题解：
对于每一种宗教都维护一棵线段树，每次在对应的线段树上查询和与最大值即可。修改的话同样如此。剩下便是树剖干的事情。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int nxt,to; }edge[maxn*2]; int head[maxn]; int n,q; int x,y; struct node1{ int rc,lc; long long maxx,sum; }tree[maxn*21]; int root[maxn]; int faith[maxn]; int level[maxn]; char opt[666]; int cnt; void add(int x,int y){ edge[++cnt].nxt=head[x]; edge[cnt].to=y; head[x]=cnt; } int dep[maxn],fa[maxn],siz[maxn],son[maxn]; void dfs1(int x,int f){ dep[x]=dep[f]+1; fa[x]=f; siz[x]=1; int maxson=-1; for(register int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa[x]) continue; dfs1(v,x); siz[x]+=siz[v]; if(siz[v]>maxson){ maxson=siz[v]; son[x]=v; } } } int top[maxn],id[maxn],in; void dfs2(int x,int topf){ top[x]=topf; id[x]=++in; if(!son[x]) return; dfs2(son[x],topf); for(register int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa[x]||v==son[x]) continue; dfs2(v,v); } } int tot; void build(int &rt,int l,int r,int v,int pos){ if(!rt) rt=++tot; if(l==pos&&pos==r){ tree[rt].maxx=v; tree[rt].sum=v; return; } int mid=(l+r)>>1; if(pos<=mid) build(tree[rt].lc,l,mid,v,pos); else build(tree[rt].rc,mid+1,r,v,pos); tree[rt].maxx=max(tree[tree[rt].lc].maxx,tree[tree[rt].rc].maxx); tree[rt].sum=tree[tree[rt].lc].sum+tree[tree[rt].rc].sum; } void clear(int rt){ tree[rt].lc=0; tree[rt].rc=0; tree[rt].maxx=0; tree[rt].sum=0; } void del(int &rt,int l,int r,int pos){ if(l==r){ clear(rt); rt=0; return; } int mid=(l+r)>>1; if(pos<=mid) del(tree[rt].lc,l,mid,pos); else del(tree[rt].rc,mid+1,r,pos); tree[rt].maxx=max(tree[tree[rt].lc].maxx,tree[tree[rt].rc].maxx); tree[rt].sum=tree[tree[rt].lc].sum+tree[tree[rt].rc].sum; if(!tree[rt].rc&&!tree[rt].lc){ clear(rt); rt=0; } } long long querymax(int rt,int l,int r,int l1,int r1){ if(!rt) return 0; if(l>=l1&&r<=r1) return tree[rt].maxx; int mid=(l+r)>>1; long long ans=0; if(l1<=mid) ans=max(ans,querymax(tree[rt].lc,l,mid,l1,r1)); if(r1>mid) ans=max(ans,querymax(tree[rt].rc,mid+1,r,l1,r1)); return ans; } long long querysum(int rt,int l,int r,int l1,int r1){ if(!rt) return 0; if(l>=l1&&r<=r1) return tree[rt].sum; int mid=(l+r)>>1; long long ans=0; if(l1<=mid) ans+=querysum(tree[rt].lc,l,mid,l1,r1); if(r1>mid) ans+=querysum(tree[rt].rc,mid+1,r,l1,r1); return ans; } long long linkmax(int x,int y){ int start=faith[x]; long long ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans=max(ans,querymax(root[start],1,n,id[top[x]],id[x])); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); ans=max(ans,querymax(root[start],1,n,id[y],id[x])); return ans; } long long linksum(int x,int y){ int start=faith[x]; long long ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=querysum(root[start],1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); ans+=querysum(root[start],1,n,id[y],id[x]); return ans; } void linkup1(int x,int y){ level[x]=y; build(root[faith[x]],1,n,level[x],id[x]); } void linkup2(int x,int y){ del(root[faith[x]],1,n,id[x]); faith[x]=y; build(root[faith[x]],1,n,level[x],id[x]); } int main(){ scanf("%d%d",&n,&q); for(register int i=1;i<=n;i++) scanf("%d%d",&level[i],&faith[i]); for(register int i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs1(1,0); dfs2(1,1); for(register int i=1;i<=n;i++) build(root[faith[i]],1,n,level[i],id[i]); for(register int i=1;i<=q;i++){ scanf("%s",opt); scanf("%d%d",&x,&y); if(opt[0]=='C'){ if(opt[1]=='C') linkup2(x,y); else linkup1(x,y); } if(opt[0]=='Q'){ if(opt[1]=='M') printf("%lld\n",linkmax(x,y)); else printf("%lld\n",linksum(x,y)); } } return 0; }