滑稽树上滑稽果，滑稽树下你和我，滑稽树前做游戏，滑稽树后做交易，滑稽多又多 又到了众望所归的滑稽时刻 今天我们将面对的，是恶名昭著的树上滑稽 它有着n个滑稽果和编号为1~n-1的n-1条滑稽枝，每一条滑稽枝都连接着两个滑稽果并且有着自己的滑稽指数 滑稽大军为了变得和它一样滑稽打倒它，将有以下两种形式的任务发布： （1）CHANGE i ti：滑稽指挥部需要你使用滑稽剑将编号为i的滑稽枝的滑稽指数变为ti （2）QUERY a b：为了获得滑稽果，成就滑稽圣打倒滑稽树，滑稽指挥部需要你汇报编号为a和编号为b的两个滑稽果之间的滑稽枝的最大滑稽指数
滑稽任务栏 第一行输入包含一个整数T，即滑稽树的数量（T <= 20） 对于每一棵滑稽树 在第一行中有一个整数N（N <= 10000），代表滑稽果的数量 在接下来的N-1行中，第i行描述编号为i的滑稽枝 每行三个整数的行a，b，c表示编号为a的滑稽果与编号为b的滑稽果之间连着一条滑稽指数为c（c <= 1000000）的滑稽枝 以下每一行包含一次滑稽指挥部形如“CHANGE i ti”或“QUERY a b”的指令 当你成功的变得和滑稽树一样滑稽打倒滑稽树时 滑稽指挥部会滑稽的显示字符串“DONE”
滑稽汇报栏 对于滑稽指挥部的每一次“QUERY a b”询问，汇报一行一个整数，即所求的滑稽指数 某次成功的进攻记录
旧·滑稽任务栏 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE
旧·滑稽汇报栏 1 3
#include<bits/stdc++.h> using namespace std; #define maxn 100010 #define INF 0x3f3f3f3f struct Edge{ int to,w,nxt; }edge[maxn<<2]; struct Edg{ int u,v,w; }edg[maxn<<2]; struct Tree{ int l,r,sum,lazy; }tree[maxn<<2]; int n,m,p,a[maxn],d[maxn],id[maxn],rk[maxn],size[maxn],head[maxn],pre[maxn],top[maxn],son[maxn]; char op[100]; int tot=0,cnt=0; void add(int u,int v,int w){ edge[++tot].to=v; edge[tot].w=w; edge[tot].nxt=head[u]; head[u]=tot; edge[++tot].to=u; edge[tot].w=w; edge[tot].nxt=head[v]; head[v]=tot; } void pushup(int k){ tree[k].sum=max(tree[k<<1].sum,tree[k<<1|1].sum); } void build(int l,int r,int k){ tree[k].l=l; tree[k].r=r; if(l==r){ tree[k].sum=a[rk[l]]; return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); pushup(k); } void dfs1(int x,int fa,int depth,int val){ pre[x]=fa; d[x]=depth; size[x]=1; a[x]=val; for(int i=head[x];~i;i=edge[i].nxt){ int to=edge[i].to,w=edge[i].w; if(to==fa) continue; dfs1(to,x,depth+1,w); size[x]+=size[to]; if(size[to]>size[son[x]]) son[x]=to; } } void dfs2(int x,int tp){ top[x]=tp; id[x]=++cnt; rk[cnt]=x; if(son[x]) dfs2(son[x],tp); for(int i=head[x];~i;i=edge[i].nxt){ int to=edge[i].to; if(to!=pre[x]&&to!=son[x]) dfs2(to,to); } } void update(int pos,int val,int k){ if(tree[k].l==pos && tree[k].r==pos){ tree[k].sum=val; return; } int mid=(tree[k].l+tree[k].r)>>1; if(pos<=mid) update(pos,val,k<<1); else update(pos,val,k<<1|1); pushup(k); } int query(int l,int r,int k){ if(tree[k].r<l||tree[k].l>r) return 0; if(l<=tree[k].l&&tree[k].r<=r) return tree[k].sum; int mid=(tree[k].l+tree[k].r)>>1,res=-INF; if(l<=mid) res=max(res,query(l,r,k<<1)); if(r> mid) res=max(res,query(l,r,k<<1|1)); return res; } int sum(int x,int y){ int res=-INF; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); res=max(res,query(id[top[x]],id[x],1)); //这里多写了个return，wa了两小时，QWQ x=pre[top[x]]; } if(x==y) return res; if(id[x]>id[y]) swap(x,y); //树剖+边权一定要加上 return res=max(res,query(id[son[x]],id[y],1)); //记住这里改为id[son[x]] } int main(){ int t; scanf("%d",&t); while(t--){ tot=0,cnt=0; scanf("%d",&n); memset(head,-1,sizeof(head)); memset(size, 0,sizeof(size)); memset(son , 0,sizeof(son )); for(int i=1;i<n;i++){ scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w); add(edg[i].u,edg[i].v,edg[i].w); } dfs1(1,-1,1,-INF); dfs2(1,1); build(1,n,1); while(1){ scanf("%s",&op); if(op[0]=='D') break; int a,b; scanf("%d%d",&a,&b); if(op[0]=='C'){ if(d[edg[a].u]>d[edg[a].v]) update(id[edg[a].u],b,1); else update(id[edg[a].v],b,1); } else printf("%d\n",sum(a,b)); } } return 0; }