Description
Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。
Input
输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0...N − 1。接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1...N − 1。|w| <= 1000。输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。接下来有M 行，每行描述了一个操作，操作有如下五种形式： C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。 N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。 SUM u v，表示询问从景点u 到v 所获得的总愉悦度。 MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。 MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。
Output
对于每一个询问(操作S、MAX 和MIN)，输出答案。
Sample Input
3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2
Sample Output
3
2
1
-1
5
3
HINT
一共有10 个数据，对于第i (1 <= i <= 10) 个数据， N = M = i * 2000。
题目分析
树剖板子题......
基础操作大综合QAQ
我们维护区间最小值 区间最大值 区间和 反转标记
反转的话 就是区间和取相反数 交换区间最小值 区间最大值并取反
记得反转标记可以抵消
最后注意查询最大值时 ???设为极小值,例如−0?7?7?7?7?
剩下的操作就考验你的码力了……
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot;
struct road
{
int x,y;
}way[20100];
struct your
{
int x,y;
int sum;
int maxx,minn;
int add;
}a[800000];
int cnt;
int head[20100],to[40100],val[40100],net[40100];
int valu[20100],value[20100],top[40100],deep[40100],fa[40100],son[40100],size[40100],number[40100];
void add(int x,int y,int c)
{
net[++tot]=head[x];
to[tot]=y;
val[tot]=c;
head[x]=tot;
}
void dfs(int x,int temp)
{
deep[x]=deep[temp]+1;
fa[x]=temp;
size[x]=1;
for(int i=head[x];i;i=net[i])
if(to[i]!=temp)
{
valu[to[i]]=val[i];
dfs(to[i],x);
if(size[son[x]]<size[to[i]]) son[x]=to[i];
size[x]+=size[to[i]];
}
}
void dfs2(int x,int temp)
{
number[x]=++cnt;
value[cnt]=valu[x];
top[x]=temp;
if(son[x]) dfs2(son[x],temp);
for(int i=head[x];i;i=net[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
void pushdown(int num)
{
a[num<<1].add=(a[num<<1].add+1)%2;
a[num<<1|1].add=(a[num<<1|1].add+1)%2;
a[num<<1].sum=-a[num<<1].sum;
a[num<<1|1].sum=-a[num<<1|1].sum;
swap(a[num<<1].maxx,a[num<<1].minn);
swap(a[num<<1|1].maxx,a[num<<1|1].minn);
a[num<<1].maxx=-a[num<<1].maxx,a[num<<1].minn=-a[num<<1].minn;
a[num<<1|1].maxx=-a[num<<1|1].maxx,a[num<<1|1].minn=-a[num<<1|1].minn;
a[num].add=0;
}
void build(int dx,int dy,int num)
{
a[num].x=dx,a[num].y=dy;
if(dx==dy)
{
a[num].sum=a[num].minn=a[num].maxx=value[dx];
return ;
}
int mid=(dx+dy)>>1;
build(dx,mid,num<<1);
build(mid+1,dy,num<<1|1);
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
a[num].minn=min(a[num<<1].minn,a[num<<1|1].minn);
return ;
}
void update(int dx,int dy,int c,int num,int color)
{
if(dx==a[num].x&&a[num].y==dy)
{
if(color==0) a[num].sum=a[num].minn=a[num].maxx=c;
else
{
a[num].add+=1;
a[num].add%=2;
a[num].sum=-a[num].sum;
swap(a[num].minn,a[num].maxx);
a[num].minn=-a[num].minn,a[num].maxx=-a[num].maxx;
}
return ;
}
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) update(dx,dy,c,num<<1|1,color);
else if(dy<=mid) update(dx,dy,c,num<<1,color);
else update(dx,mid,c,num<<1,color),update(mid+1,dy,c,num<<1|1,color);
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
a[num].maxx=max(a[num<<1].maxx,a[num<<1|1].maxx);
a[num].minn=min(a[num<<1].minn,a[num<<1|1].minn);
}
int ask(int dx,int dy,int num,int color)
{
if(a[num].x==dx&&a[num].y==dy)
{
if(color==1) return a[num].sum;
if(color==2) return a[num].maxx;
if(color==3) return a[num].minn;
}
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) return ask(dx,dy,num<<1|1,color);
else if(dy<=mid) return ask(dx,dy,num<<1,color);
else
{
if(color==1) return ask(dx,mid,num<<1,color)+ask(mid+1,dy,num<<1|1,color);
if(color==2) return max(ask(dx,mid,num<<1,color),ask(mid+1,dy,num<<1|1,color));
if(color==3) return min(ask(dx,mid,num<<1,color),ask(mid+1,dy,num<<1|1,color));
}
}
void change(int x,int y,int c,int color)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
update(number[top[x]],number[x],c,1,color);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
if(x!=y) update(number[x]+1,number[y],c,1,color);
}
int find(int x,int y,int color)
{
int Sum=0,Maxx=-0x7f7f7f7f,Minn=0x7f7f7f7f;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
if(color==1) Sum+=ask(number[top[x]],number[x],1,color);
if(color==2) Maxx=max(ask(number[top[x]],number[x],1,color),Maxx);
if(color==3) Minn=min(ask(number[top[x]],number[x],1,color),Minn);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
if(x==y)
{
if(color==1) return Sum;
if(color==2) return Maxx;
if(color==3) return Minn;
}
if(color==1) { Sum+=ask(number[x]+1,number[y],1,color); return Sum; }
if(color==2) { Maxx=max(Maxx,ask(number[x]+1,number[y],1,color)); return Maxx; }
if(color==3) { Minn=min(Minn,ask(number[x]+1,number[y],1,color)); return Minn; }
}
char s[5];
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
x++,y++;
add(x,y,c);add(y,x,c);
way[i].x=x,way[i].y=y;
}
dfs(1,0),dfs2(1,1);
build(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%s",&s[0]);
if(s[0]=='S')
scanf("%d%d",&x,&y),x++,y++,printf("%d\n",find(x,y,1));
if(s[1]=='A')
scanf("%d%d",&x,&y),x++,y++,printf("%d\n",find(x,y,2));
if(s[1]=='I')
scanf("%d%d",&x,&y),x++,y++,printf("%d\n",find(x,y,3));
if(s[0]=='N')
scanf("%d%d",&x,&y),x++,y++,change(x,y,0,1);
if(s[0]=='C')
{
scanf("%d%d",&x,&y);
if(deep[way[x].x]>deep[way[x].y]) swap(way[x].x,way[x].y);
change(way[x].x,way[x].y,y,0);
}
}
return 0;
}
