题解：
树链剖分+修改
修改和查找操作差不多
代码：
#include <cstring> #include <cstdio> #include <algorithm> #include <cstdio> #include <cstdlib> using namespace std; const int N=10005; struct Edge { int cnt,y[N*2],z[N*2],nxt[N*2],fst[N]; void clear() { cnt=0; memset(fst,0,sizeof fst); } void add(int a,int b,int c) { y[++cnt]=b;z[cnt]=c; nxt[cnt]=fst[a];fst[a]=cnt; } }g; struct edge { int a,b,c; }e[N]; int T,n,fa[N],size[N],fadis[N],depth[N],son[N],top[N],p[N],ap[N],cnp; struct Tree { int ma,mi,add; }t[N*4]; void Get_Gen_Info(int rt,int pre,int d) { depth[rt]=d,fa[rt]=pre,size[rt]=1,son[rt]=-1; for (int i=g.fst[rt];i;i=g.nxt[i]) if (g.y[i]!=pre) { int s=g.y[i]; Get_Gen_Info(s,rt,d+1); fadis[s]=g.z[i]; size[rt]+=size[s]; if (son[rt]==-1||size[s]>size[son[rt]])son[rt]=s; } } void Get_Pos(int rt,int tp) { top[rt]=tp,p[rt]=++cnp,ap[cnp]=rt; if (son[rt]==-1)return; else Get_Pos(son[rt],tp); for (int i=g.fst[rt];i;i=g.nxt[i]) { int s=g.y[i]; if (s!=fa[rt]&&s!=son[rt])Get_Pos(s,s); } } void pushup(int rt) { int ls=rt<<1,rs=ls|1; t[rt].mi=min(t[ls].mi,t[rs].mi); t[rt].ma=max(t[ls].ma,t[rs].ma); } void build(int rt,int le,int ri) { t[rt].add=0; if (le==ri) { t[rt].ma=t[rt].mi=fadis[ap[le]]; return; } int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; build(ls,le,mid); build(rs,mid+1,ri); pushup(rt); } void fz(int &x,int &y) { x=-x,y=-y; swap(x,y); } void pushdown(int rt) { int &a=t[rt].add; int ls=rt<<1,rs=ls|1; if (a==0)return; t[ls].add^=1,t[rs].add^=1; fz(t[ls].ma,t[ls].mi); fz(t[rs].ma,t[rs].mi); a=0; } void change(int rt,int le,int ri,int pos,int v) { if (le==ri) { t[rt].mi=t[rt].ma=v; return; } pushdown(rt); int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; if (pos<=mid)change(ls,le,mid,pos,v); else change(rs,mid+1,ri,pos,v); pushup(rt); } void update(int rt,int le,int ri,int xle,int xri) { if (le>xri||ri<xle)return; if (xle<=le&&ri<=xri) { t[rt].add^=1; fz(t[rt].ma,t[rt].mi); return; } pushdown(rt); int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; update(ls,le,mid,xle,xri); update(rs,mid+1,ri,xle,xri); pushup(rt); } int query(int rt,int le,int ri,int xle,int xri) { if (le>xri||ri<xle)return -1e9; if (xle<=le&&ri<=xri)return t[rt].ma; pushdown(rt); int mid=(le+ri)>>1,ls=rt<<1,rs=ls|1; return max(query(ls,le,mid,xle,xri),query(rs,mid+1,ri,xle,xri)); } void fupdate(int a,int b) { int f1=top[a],f2=top[b]; while (f1!=f2) { if (depth[f1]<depth[f2])swap(f1,f2),swap(a,b); update(1,1,n,p[f1],p[a]); a=fa[f1],f1=top[a]; } if (a==b)return; if (depth[a]>depth[b])swap(a,b); update(1,1,n,p[son[a]],p[b]); } int find(int a,int b) { int f1=top[a],f2=top[b],ans=-1e9; while (f1!=f2) { if (depth[f1]<depth[f2])swap(f1,f2),swap(a,b); ans=max(ans,query(1,1,n,p[f1],p[a])); a=fa[f1],f1=top[a]; } if (a==b)return ans; if (depth[a]>depth[b])swap(a,b); return max(ans,query(1,1,n,p[son[a]],p[b])); } int main() { scanf("%d",&T); while (T--) { scanf("%d",&n); g.clear(); for (int i=1,a,b,c;i<n;i++) { scanf("%d%d%d",&a,&b,&c); g.add(a,b,c); g.add(b,a,c); e[i].a=a,e[i].b=b,e[i].c=c; } cnp=0,fadis[1]=0; Get_Gen_Info(1,0,0); Get_Pos(1,1); build(1,1,n); for (int i=1;i<n;i++) if (depth[e[i].a]>depth[e[i].b])swap(e[i].a,e[i].b); char str[10]; int a,b; while (scanf("%s",str)&&str[0]!='D') { scanf("%d%d",&a,&b); if (str[0]=='C')change(1,1,n,p[e[a].b],b); else if (str[0]=='N')fupdate(a,b); else printf("%d ",find(a,b)); } } return 0; }