Description
You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:
CHANGE i v Change the weight of the ith edge to v
NEGATE a b Negate the weight of every edge on the path from a to b
QUERY a b Find the maximum weight of edges on the path from a to b
Input
The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.
Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.
Output
For each “QUERY” instruction, output the result on a separate line.
Sample Input
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Sample Output
1
3
分析：
树链剖分
样例输入2
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
NEGATE 1 2
QUERY 1 2
DONE
样例输出2
1
3
-3
tip
题目中的
NEGATE这个操作是取反
（zz，看了半天题目）
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=0x33333333;
const int N=10010;
struct node{
int x,y,v,nxt;
};
node way[N<<1];
int n,cnt=0,val[N],pre[N],deep[N],st[N],tot=0,son[N],top[N],num[N],shu[N],wz[N],size[N];
struct nd{
int x,y,mx,la,mn;
};
nd t[N<<2];
void add(int u,int w,int z)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].v=z;way[tot].nxt=st[w];st[w]=tot;
}
void dfs1(int now,int fa,int dep)
{
pre[now]=fa;
deep[now]=dep;
size[now]=1;
son[now]=0;
int mx=0;
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=fa)
{
dfs1(way[i].y,now,dep+1);
val[way[i].y]=way[i].v; wz[(i+1)/2]=way[i].y;
size[now]+=size[way[i].y];
if (size[way[i].y]>mx)
{
mx=size[way[i].y];
son[now]=way[i].y;
}
}
}
void dfs2(int now,int fa)
{
if (son[fa]!=now) top[now]=now;
else top[now]=top[fa];
num[now]=++cnt; shu[num[now]]=now;
if (son[now])
{
dfs2(son[now],now);
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=fa&&way[i].y!=son[now])
dfs2(way[i].y,now);
}
}
void update(int bh)
{
t[bh].mx=max(t[bh<<1].mx,t[bh<<1|1].mx);
t[bh].mn=min(t[bh<<1].mn,t[bh<<1|1].mn);
}
void build(int bh,int l,int r)
{
t[bh].x=l;t[bh].y=r;
t[bh].mx=-INF;
t[bh].mn=INF;
t[bh].la=0;
if (l==r)
{
if (l!=1){
t[bh].mx=t[bh].mn=val[shu[l]];
}
return;
}
int mid=(l+r)>>1;
build(bh<<1,l,mid);
build(bh<<1|1,mid+1,r);
update(bh);
}
void rotate(int bh)
{
t[bh].mx*=-1;
t[bh].mn*=-1;
swap(t[bh].mn,t[bh].mx);
}
void push(int bh)
{
if (t[bh].la&&t[bh].x!=t[bh].y)
{
t[bh<<1].la^=1;
rotate(bh<<1);
t[bh<<1|1].la^=1;
rotate(bh<<1|1);
t[bh].la^=1;
}
}
void change(int bh,int wz,int z)
{
push(bh);
if (t[bh].x==t[bh].y)
{
t[bh].mx=t[bh].mn=z;
return;
}
int mid=(t[bh].x+t[bh].y)>>1;
if (wz<=mid) change(bh<<1,wz,z);
else change(bh<<1|1,wz,z);
update(bh);
}
int ask(int bh,int l,int r)
{
push(bh); //
if (t[bh].x>=l&&t[bh].y<=r)
{
return t[bh].mx;
}
int mid=(t[bh].x+t[bh].y)>>1;
int ans=-INF;
if (l<=mid) ans=max(ans,ask(bh<<1,l,r));
if (r>mid) ans=max(ans,ask(bh<<1|1,l,r));
return ans;
}
int askmax(int u,int w)
{
int f1=top[u];
int f2=top[w];
int ans=-INF;
while (f1!=f2)
{
if (deep[f1]<deep[f2]) swap(u,w),swap(f1,f2);
ans=max(ans,ask(1,num[f1],num[u]));
u=pre[f1];
f1=top[u];
}
if (u==w) return ans;
if (num[u]>num[w]) swap(u,w);
ans=max(ans,ask(1,num[son[u]],num[w]));
return ans==-INF? 0:ans; ///
}
void gg(int bh,int l,int r)
{
push(bh);
if (t[bh].x>=l&&t[bh].y<=r)
{
t[bh].la=1;
rotate(bh); //取反
return;
}
int mid=(t[bh].x+t[bh].y)>>1;
if (l<=mid) gg(bh<<1,l,r);
if (r>mid) gg(bh<<1|1,l,r);
update(bh);
}
void fan(int u,int w)
{
int f1=top[u];
int f2=top[w];
while (f1!=f2)
{
if (deep[f1]<deep[f2]) swap(u,w),swap(f1,f2);
gg(1,num[f1],num[u]);
u=pre[f1];
f1=top[u];
}
if (u==w) return;
if (num[u]>num[w]) swap(u,w);
gg(1,num[son[u]],num[w]);
return;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
memset(st,0,sizeof(st)); //laji的初始化
memset(t,0,sizeof(t));
memset(deep,0,sizeof(deep));
memset(shu,0,sizeof(shu));
memset(num,0,sizeof(num));
tot=0; cnt=0;
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z);
add(u,w,z);
}
char opt[10];
dfs1(1,0,1);
dfs2(1,0);
build(1,1,n);
scanf("%s",&opt);
while (opt[0]!='D')
{
int u,w;
scanf("%d%d",&u,&w);
if (opt[0]=='C')
change(1,num[wz[u]],w);
else if (opt[0]=='N')
fan(u,w);
else if (opt[0]=='Q')
printf("%d
",askmax(u,w));
scanf("%s",&opt);
}
}
return 0;
}