题解：
树链剖分的模板题
具体代码详见网上的其他代码
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=400005; char s[100]; int data[N],p[N],n,pos,fp[N],num[N]; int x,y,z,tot,top[N],T,e[N][3],val[N],deep[N],son[N],fa[N],ne[N],fi[N],zz[N]; void jb(int x,int y) { ne[++tot]=fi[x]; fi[x]=tot; zz[tot]=y; } void dfs1(int x,int y,int z) { deep[x]=z; fa[x]=y; for (int i=fi[x];i;i=ne[i]) { int k=zz[i]; if (k!=y) { dfs1(k,x,z+1); num[x]+=num[k]; if (son[x]==-1||(num[son[x]]<num[k]))son[x]=k; } } } void dfs2(int x,int y) { top[x]=y; if (son[x]!=-1) { p[x]=pos++; fp[p[x]]=x; dfs2(son[x],y); } else { p[x]=pos++; fp[p[x]]=x; return; } for (int i=fi[x];i;i=ne[i]) if (zz[i]!=son[x]&&zz[i]!=fa[x]) dfs2(zz[i],zz[i]); } void pushup(int x) { data[x]=max(data[x*2],data[x*2+1]); } void build(int l,int r,int x) { if (l==r) { data[x]=val[l]; return; } int mid=(l+r)/2; build(l,mid,x*2); build(mid+1,r,x*2+1); pushup(x); } void updata(int p,int q,int l,int r,int x) { if (l==r) { data[x]=q; return; } int mid=(l+r)/2; if (p<=mid)updata(p,q,l,mid,x*2); else updata(p,q,mid+1,r,x*2+1); pushup(x); } int query(int x,int y,int l,int r,int s) { if (x>r||y<l)return 0; if (x<=l&&y>=r)return data[s]; int mid=(l+r)/2; return max(query(x,y,l,mid,s*2),query(x,y,mid+1,r,s*2+1)); } int find(int x,int y) { int f1=top[x],f2=top[y],temp=0; while (f1!=f2) { if (deep[f1]<deep[f2]) { swap(x,y); swap(f1,f2); } temp=max(temp,query(p[f1],p[x],1,n,1)); x=fa[f1],f1=top[x]; } if (x==y)return temp; if (deep[x]>deep[y])swap(x,y); return max(temp,query(p[son[x]],p[y],1,n,1)); } int read() { int x=0;char c; for (;c<'0'||c>'9';c=getchar()); for (;c>='0'&&c<='9';c=getchar())x=x*10+c-48; return x; } int main() { scanf("%d",&T); while (T--) { pos=1;tot=0; memset(fi,0,sizeof fi); memset(son,-1,sizeof son); memset(data,0,sizeof data); scanf("%d",&n); for (int i=0;i<n-1;i++) { scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); jb(e[i][0],e[i][1]);jb(e[i][1],e[i][0]); } dfs1(1,0,0); dfs2(1,1); for (int i=0;i<n-1;i++) { if (deep[e[i][0]]<deep[e[i][1]])swap(e[i][0],e[i][1]); val[p[e[i][0]]]=e[i][2]; } build(1,n,1); while (scanf("%s",&s)) { if (s[0]=='D')break; x=read();y=read(); if (s[0]=='Q')printf("%d ",find(x,y)); else updata(p[e[x-1][0]],y,1,n,1); } } return 0; }