树剖裸题，当然LCT也可以。
树剖：
1 #include<cstdio> 2 #include<algorithm> 3 #define ls (x<<1) 4 #define rs (ls|1) 5 #define lson ls,L,mid 6 #define rson rs,mid+1,R 7 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 8 #define For(i,x) for (int i=h[x],k; i; i=nxt[i]) 9 using namespace std; 10 11 const int N=20010; 12 char op[10]; 13 int n,Q,u,v,w,tim,cnt,id[N],z[N],pos[N],pre[N],fa[N],dep[N],sz[N],son[N],top[N],dfn[N]; 14 int h[N],to[N<<1],nxt[N<<1],val[N<<1],mn[N<<2],mx[N<<2],sm[N<<2],tag[N<<2]; 15 16 void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; } 17 18 void dfs(int x){ 19 sz[x]=1; dep[x]=dep[fa[x]]+1; 20 For(i,x) if ((k=to[i])!=fa[x]){ 21 fa[k]=x; pre[k]=val[i]; id[val[i]]=k; dfs(k); sz[x]+=sz[k]; 22 if (sz[k]>sz[son[x]]) son[x]=k; 23 } 24 } 25 26 void dfs2(int x,int tp){ 27 top[x]=tp; dfn[x]=++tim; pos[tim]=x; 28 if (son[x]) dfs2(son[x],tp); 29 For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]) dfs2(k,k); 30 } 31 32 void upd(int x){ sm[x]=sm[ls]+sm[rs]; mx[x]=max(mx[ls],mx[rs]); mn[x]=min(mn[ls],mn[rs]); } 33 void put(int x){ sm[x]=-sm[x]; int t=mx[x]; mx[x]=-mn[x]; mn[x]=-t; tag[x]^=1; } 34 35 void push(int x){ if (tag[x]) put(ls),put(rs),tag[x]=0; } 36 37 void build(int x,int L,int R){ 38 if (L==R){ sm[x]=mn[x]=mx[x]=z[pre[pos[L]]]; return; } 39 int mid=(L+R)>>1; 40 build(lson); build(rson); upd(x); 41 } 42 43 void mdf(int x,int L,int R,int p,int k){ 44 if (L==R){ sm[x]=mn[x]=mx[x]=k; return; } 45 int mid=(L+R)>>1; push(x); 46 if (p<=mid) mdf(lson,p,k); else mdf(rson,p,k); 47 upd(x); 48 } 49 50 void Rev(int x,int L,int R,int l,int r){ 51 if (L==l && r==R){ put(x); return; } 52 int mid=(L+R)>>1; push(x); 53 if (r<=mid) Rev(lson,l,r); 54 else if (l>mid) Rev(rson,l,r); 55 else Rev(lson,l,mid),Rev(rson,mid+1,r); 56 upd(x); 57 } 58 59 int que(int x,int L,int R,int l,int r,int k){ 60 if (L==l && r==R) return k==2?mn[x]:k?mx[x]:sm[x]; 61 int mid=(L+R)>>1; push(x); 62 if (r<=mid) return que(lson,l,r,k); 63 else if (l>mid) return que(rson,l,r,k); 64 else{ 65 int mid=(L+R)>>1,t1=que(lson,l,mid,k),t2=que(rson,mid+1,r,k); 66 return k==2 ? min(t1,t2) : k==1 ? max(t1,t2) : t1+t2; 67 } 68 } 69 70 void work(int x,int y){ 71 for (; top[x]!=top[y]; x=fa[top[x]]){ 72 if (dep[top[x]]<dep[top[y]]) swap(x,y); 73 Rev(1,1,n,dfn[top[x]],dfn[x]); 74 } 75 if (x==y) return; 76 if (dep[x]<dep[y]) swap(x,y); 77 Rev(1,1,n,dfn[y]+1,dfn[x]); 78 } 79 80 int solve(int x,int y,int k){ 81 int res=0; 82 if (k==1) res=-1001; 83 if (k==2) res=1001; 84 for (; top[x]!=top[y]; x=fa[top[x]]){ 85 if (dep[top[x]]<dep[top[y]]) swap(x,y); 86 int t=que(1,1,n,dfn[top[x]],dfn[x],k); 87 if (k==0) res+=t; 88 if (k==1) res=max(res,t); 89 if (k==2) res=min(res,t); 90 } 91 if (x==y) return res; 92 if (dep[x]<dep[y]) swap(x,y); 93 int t=que(1,1,n,dfn[y]+1,dfn[x],k); 94 if (k==0) res+=t; 95 if (k==1) res=max(res,t); 96 if (k==2) res=min(res,t); 97 return res; 98 } 99 100 int main(){ 101 freopen("bzoj2157.in","r",stdin); 102 freopen("bzoj2157.out","w",stdout); 103 scanf("%d",&n); 104 rep(i,2,n) scanf("%d%d%d",&u,&v,&w),u++,v++,add(u,v,i),add(v,u,i),z[i]=w; 105 dfs(1); dfs2(1,1); build(1,1,n); 106 for (scanf("%d",&Q); Q--; ){ 107 scanf("%s%d%d",op,&u,&v); u++; v++; 108 if (op[0]=='C') mdf(1,1,n,dfn[id[u]],v-1); 109 if (op[0]=='N') work(u,v); 110 if (op[0]=='S') printf("%d ",solve(u,v,0)); 111 if (op[1]=='A') printf("%d ",solve(u,v,1)); 112 if (op[1]=='I') printf("%d ",solve(u,v,2)); 113 } 114 return 0; 115 }
LCT:
1 #include<cstdio> 2 #include<algorithm> 3 #define ls c[x][0] 4 #define rs c[x][1] 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 using namespace std; 7 8 const int N=40010; 9 char op[10]; 10 int n,Q,nd,x,y,w,v[N],c[N][2],f[N],rev[N],tag[N],sm[N],mn[N],mx[N]; 11 12 bool isrt(int x){ return !f[x] || (c[f[x]][0]!=x && c[f[x]][1]!=x); } 13 14 void upd(int x){ 15 sm[x]=sm[ls]+sm[rs]+v[x]; 16 mn[x]=min(min(mn[ls],mn[rs]),x>n?v[x]:1001); 17 mx[x]=max(max(mx[ls],mx[rs]),x>n?v[x]:-1001); 18 } 19 20 void put(int x){ if (!x) return; v[x]=-v[x]; sm[x]=-sm[x]; int t=mx[x]; mx[x]=-mn[x]; mn[x]=-t; tag[x]^=1; } 21 void Rev(int x){ if (!x) return; rev[x]^=1; swap(ls,rs); } 22 23 void push(int x){ 24 if (rev[x]) Rev(ls),Rev(rs),rev[x]=0; 25 if (tag[x]) put(ls),put(rs),tag[x]=0; 26 } 27 28 void pd(int x){ if (!isrt(x)) pd(f[x]); push(x); } 29 30 void rot(int x){ 31 int y=f[x],z=f[y],w=c[y][1]==x; 32 if (!isrt(y)) c[z][c[z][1]==y]=x; 33 f[x]=z; f[y]=x; f[c[x][w^1]]=y; 34 c[y][w]=c[x][w^1]; c[x][w^1]=y; upd(y); 35 } 36 37 void splay(int x){ 38 for (pd(x); !isrt(x); rot(x)){ 39 int y=f[x],z=f[y]; 40 if (!isrt(y)) rot((c[z][0]==y)^(c[y][0]==x) ? x : y); 41 }upd(x); 42 } 43 44 void access(int x){ for (int y=0; x; y=x,x=f[x]) splay(x),c[x][1]=y,upd(x); } 45 void mkrt(int x){ access(x); splay(x); Rev(x); } 46 int split(int x,int y){ mkrt(x); access(y); splay(y); return y; } 47 void link(int x,int y){ mkrt(x); f[x]=y; } 48 49 int main(){ 50 freopen("bzoj2157.in","r",stdin); 51 freopen("bzoj2157.out","w",stdout); 52 scanf("%d",&n); 53 rep(i,0,n) mn[i]=1001,mx[i]=-1001; 54 rep(i,1,n-1) scanf("%d%d%d",&x,&y,&w),x++,y++,v[n+i]=w,upd(n+i),link(n+i,x),link(n+i,y); 55 for (scanf("%d",&Q); Q--; ){ 56 scanf("%s%d%d",op,&x,&y); x++; y++; 57 if (op[0]=='C') splay(x+n-1),v[x+n-1]=y-1,upd(x+n-1); 58 if (op[0]=='N') put(split(x,y)); 59 if (op[0]=='S') printf("%d ",sm[split(x,y)]); 60 if (op[1]=='A') printf("%d ",mx[split(x,y)]); 61 if (op[1]=='I') printf("%d ",mn[split(x,y)]); 62 } 63 return 0; 64 }