我的写法是动态开点线段树+树剖，只 AC 了 #3,#4,#9

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int ll
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e6+10;
int n,m;
int w[MAXN],c[MAXN];
int head[MAXN],tt=0;
struct edge
{
	int to,nxt;
}e[MAXN<<1];
void add(int x,int y)
{
	e[++tt].nxt=head[x];
	head[x]=tt;
	e[tt].to=y;
}
int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN];
void dfs1(int u,int fat)
{
	fa[u]=fat;
	dep[u]=dep[fat]+1;
	siz[u]=1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fat)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])
			son[u]=v;
	}
}
int top[MAXN],dfn[MAXN],tim=0;
void dfs2(int u,int topfa)
{
	top[u]=topfa;
	dfn[u]=++tim;
	if(son[u])
		dfs2(son[u],topfa);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa[u] || v==son[u])
			continue;
		dfs2(v,v);
	}
}
struct tree
{
	int l,r;
	int maxn,sum;
}tr[MAXN*10];
int rt[MAXN],tot=0;
void pushup(int k)
{
	tr[k].maxn=max(tr[tr[k].l].maxn,tr[tr[k].r].maxn);
	tr[k].sum=tr[tr[k].l].sum+tr[tr[k].r].sum;
}
void build(int &k,int l,int r,int x,int v)//开一个新的点 
{
	if(!k)
		k=++tot;
	if(l==r)
	{
		tr[k].maxn=tr[k].sum=v;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)
		build(tr[k].l,l,mid,x,v);
	if(x>mid)
		build(tr[k].r,mid+1,r,x,v);
	pushup(k);
}
int query1(int k,int l,int r,int x,int y)
{
	if(x<=l && r<=y)
		return tr[k].sum;
	int res=0;
	int mid=l+r>>1;
	if(x<=mid)
		res+=query1(tr[k].l,l,mid,x,y);
	if(y>mid)
		res+=query1(tr[k].r,mid+1,r,x,y);
	return res;
}
int query2(int k,int l,int r,int x,int y)
{
	if(x<=l && r<=y)
		return tr[k].sum;
	int res=-1e9;
	int mid=l+r>>1;
	if(x<=mid)
		res=max(res,query2(tr[k].l,l,mid,x,y));
	if(y>mid)
		res=max(res,query2(tr[k].r,mid+1,r,x,y));
	return res;
}
int querysum(int x,int y,int k)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res+=query1(rt[k],1,n,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	res+=query1(rt[k],1,n,dfn[x],dfn[y]);
	return res;
}
int querymax(int x,int y,int k)
{
	int res=-1e9;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		res=max(res,query2(rt[k],1,n,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	res=max(res,query2(rt[k],1,n,dfn[x],dfn[y]));
	return res;
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		w[i]=read(),c[i]=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		add(x,y),add(y,x);
	}
	dfs1(1,0),dfs2(1,0);
	for(int i=1;i<=n;i++)
		build(rt[c[i]],1,n,dfn[i],w[i]);
	for(int i=1;i<=m;i++)
	{
		string op;cin>>op;
		int x=read(),y=read();
		if(op=="CC")
		{
			build(rt[c[x]],1,n,dfn[x],0);
			c[x]=y;
			build(rt[c[x]],1,n,dfn[x],w[x]);
		}
		if(op=="CW")
		{
			build(rt[c[x]],1,n,dfn[x],y);
			w[x]=y;
		}
		if(op=="QS")
			printf("%lld\n",querysum(x,y,c[x]));
		if(op=="QM")
			printf("%lld\n",querymax(x,y,c[x]));
	}
	return 0;
}