思路

以树链剖分+主席树可解决。 要动态开点（不然的话肯定会爆啊） 然后就是对每种颜色（宗教）为根的树进行单点修改还有区间查询。 注：这道题容易被卡常，我宏定义就写炸了很多次。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;

vector<int>G[N];
inline void addedge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
}

int sz[N],fa[N],son[N],dep[N],dfn[N],idfn[N],bel[N],idx;

inline void dfs1(int x){
	sz[x]=1;
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==fa[x]) continue;
		fa[to]=x;
		dep[to]=dep[x]+1;
		dfs1(to);
		sz[x]+=sz[to];
		if(sz[son[x]]<sz[to]) son[x]=to;
	}
}

inline void dfs2(int x,int tp){
	dfn[x]=++idx;
	idfn[idx]=x;
	bel[x]=tp;
	if(son[x]) dfs2(son[x],tp);
	for(int i=0;i<G[x].size();i++){
		int to=G[x][i];
		if(to==son[x]||to==fa[x]) continue;
		dfs2(to,to); 
	}
}

#define ls tr[p].lson
#define rs tr[p].rson
#define MID int mid=l+r>>1

int rt[N],SZ;
struct node{
	int lson,rson,mx,sum;
}tr[N*24];

inline void pushup(int p){
	tr[p].sum=tr[ls].sum+tr[rs].sum;
	tr[p].mx=max(tr[ls].mx,tr[rs].mx);
}

inline void build(int &p,int l,int r,int pos,int val){
	if(!p) p=++SZ;
	if(l==r){
		tr[p].mx=tr[p].sum=val;
		return;
	}
	MID;
	if(pos<=mid) build(ls,l,mid,pos,val);
	else build(rs,mid+1,r,pos,val);
	pushup(p);
}

inline void del(int &p,int l,int r,int pos){
	if(l==r){
		tr[p].mx=tr[p].sum=p=0;
		return;
	} 
	MID;
	if(pos<=mid) del(ls,l,mid,pos);
	else del(rs,mid+1,r,pos);
	pushup(p);
	if(!ls&&!rs) tr[p].mx=tr[p].sum=p=0;
}

inline int qs(int &p,int l,int r,int ql,int qr){
	if(!p) return 0;
	if(ql<=l&&r<=qr) return tr[p].sum;
	MID;int res=0;
	if(ql<=mid) res=qs(ls,l,mid,ql,qr);
	if(qr>mid) res+=qs(rs,mid+1,r,ql,qr);
	return res;
}

inline int qm(int &p,int l,int r,int ql,int qr){
	if(!p) return 0;
	if(ql<=l&&r<=qr) return tr[p].mx; 
	MID;int res=0;
	if(ql<=mid) res=qm(ls,l,mid,ql,qr);
	if(qr>mid) res=max(res,qm(rs,mid+1,r,ql,qr));
	return res; 
}

int n,m,x,y,res,rd,tmp,val[N],col[N];
string op;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>val[i]>>col[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		addedge(x,rd=y); //随机根节点 
	}
	dfs1(rd);
	dfs2(rd,rd);
	for(int i=1;i<=n;i++) build(rt[col[idfn[i]]],1,n,i,val[idfn[i]]);
	for(int i=1;i<=m;i++){
		cin>>op>>x>>y;
		if(op=="CC"){
			del(rt[col[x]],1,n,dfn[x]);
			col[x]=y;
			build(rt[col[x]],1,n,dfn[x],val[x]); 
		}else if(op=="CW"){
			del(rt[col[x]],1,n,dfn[x]);
			val[x]=y;
			build(rt[col[x]],1,n,dfn[x],val[x]);
		}else if(op=="QS"){
			res=0;
			tmp=col[x];
			while(bel[x]!=bel[y]){
				if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
				res+=qs(rt[tmp],1,n,dfn[bel[x]],dfn[x]);
				x=fa[bel[x]];
			}
			if(dep[x]<dep[y]) swap(x,y);
			res+=qs(rt[tmp],1,n,dfn[y],dfn[x]);
			cout<<res<<"\n";
		}else{
			res=0;
			tmp=col[x];
			while(bel[x]!=bel[y]){
				if(dep[bel[x]]<dep[bel[y]]) swap(x,y);
				res=max(res,qm(rt[tmp],1,n,dfn[bel[x]],dfn[x]));
				x=fa[bel[x]];
			}
			if(dep[x]<dep[y]) swap(x,y);
			res=max(res,qm(rt[tmp],1,n,dfn[y],dfn[x]));
			cout<<res<<"\n";
		}
	}
	return 0;
}