题目描述
Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。
Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。
现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
解析
树剖裸题，但是维护相反数时要稍微注意一下，负负得正，以及值域的翻转。
参考代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 100010
#define INF 0x3f3f3f3f
using namespace std;
inline int read()
{
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
struct rec{
int next,ver,edge;
}g[N<<1];
int head[N],tot,n,cnt,m;
struct tree{
int l,r;
int max,min,sum,rem;
}t[N<<2];
inline void add(int x,int y,int val)
{
g[++tot].ver=y,g[tot].edge=val;
g[tot].next=head[x],head[x]=tot;
}
int top[N],size[N],id[N],dep[N],son[N],fa[N],w[N],wt[N];
struct node{
int u,v;
}a[N];
inline void pushup(int p)
{
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].max=max(t[p<<1].max,t[p<<1|1].max);
t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
inline void pushdown(int p)
{
if(t[p].rem){
t[p<<1].rem^=1;t[p<<1|1].rem^=1;
t[p<<1].sum*=-1;t[p<<1|1].sum*=-1;
t[p<<1].max*=-1;t[p<<1].min*=-1;
t[p<<1|1].max*=-1;t[p<<1|1].min*=-1;
swap(t[p<<1].max,t[p<<1].min);swap(t[p<<1|1].max,t[p<<1|1].min);
t[p].rem^=1;
}
}
inline void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;t[p].max=-INF,t[p].min=INF;
if(l==r){t[p].sum=t[p].max=t[p].min=w[l];return;}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
inline void change(int p,int x,int val)
{
if(t[p].l==t[p].r&&t[p].l==x){
t[p].sum=t[p].max=t[p].min=val;
t[p].rem=0;
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) change(p<<1,x,val);
else change(p<<1|1,x,val);
pushup(p);
}
inline void mirror(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r){
t[p].sum*=-1;
t[p].max*=-1;t[p].min*=-1;
swap(t[p].max,t[p].min);
t[p].rem^=1;
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) mirror(p<<1,l,r);
if(r>mid) mirror(p<<1|1,l,r);
pushup(p);
}
inline int Sum(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
int val=0;
if(l<=mid) val+=Sum(p<<1,l,r);
if(r>mid) val+=Sum(p<<1|1,l,r);
return val;
}
inline int Max(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p].max;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
int val=-INF;
if(l<=mid) val=max(val,Max(p<<1,l,r));
if(r>mid) val=max(val,Max(p<<1|1,l,r));
return val;
}
inline int Min(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p].min;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
int val=INF;
if(l<=mid) val=min(val,Min(p<<1,l,r));
if(r>mid) val=min(val,Min(p<<1|1,l,r));
return val;
}
inline void dfs1(int x,int f,int deep)
{
size[x]=1,fa[x]=f,dep[x]=deep;
int maxson=-1;
for(int i=head[x];i;i=g[i].next){
int y=g[i].ver,z=g[i].edge;
if(y==f) continue;
dfs1(y,x,deep+1);
wt[y]=z;
size[x]+=size[y];
if(maxson<size[y]) maxson=size[y],son[x]=y;
}
}
inline void dfs2(int x,int topf)
{
id[x]=++cnt,w[cnt]=wt[x],top[x]=topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=g[i].next){
int y=g[i].ver;
if(y==fa[x]||y==son[x]) continue;
dfs2(y,y);
}
}
inline void Mirror(int x,int y)
{
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
mirror(1,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
mirror(1,id[x]+1,id[y]);
}
inline int Maxx(int x,int y)
{
int res=-INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=max(res,Max(1,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=max(res,Max(1,id[x]+1,id[y]));
return res;
}
inline int Minn(int x,int y)
{
int res=INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=min(res,Min(1,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=min(res,Min(1,id[x]+1,id[y]));
return res;
}
inline int SUM(int x,int y)
{
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res+=Sum(1,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res+=Sum(1,id[x]+1,id[y]);
return res;
}
int main()
{
n=read();
for(int i=1;i<n;++i){
a[i].u=read(),a[i].v=read();
a[i].u++,a[i].v++;
int z=read();
add(a[i].u,a[i].v,z),add(a[i].v,a[i].u,z);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
m=read();
while(m--){
char op[10];
scanf("%s",op);
int x=read(),y=read();
if(op[0]=='S'){
x++,y++;
printf("%d
",SUM(x,y));
}
if(op[0]=='N'){
x++,y++;
Mirror(x,y);
}
if(op[0]=='C'){
if(fa[a[x].u]==a[x].v) change(1,id[a[x].u],y);
if(fa[a[x].v]==a[x].u) change(1,id[a[x].v],y);
}
if(op[0]=='M'){
x++,y++;
if(op[1]=='A'){
printf("%d
",Maxx(x,y));
}
else printf("%d
",Minn(x,y));
}
}
return 0;
}