我们考虑像主席树一样动态开点。（不过如果还想省空间，可以用指针，但是速度较慢。）

接下来就简单了，单点修改、区间求和、区间最值都好做。

不过在改宗教的时候，若原来的这个点在树a上，要改信宗教b，那要把这个点的所有信息复制（原来已有此点）/新建（原来无此点）到树b上，再把树a原来的位置清空。

时间复杂度O(qlog^2n)，很可过。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
namespace FastIO{//快读，卡常神器之物也。
	ll qread(){ll num=0;ll mark=1;char ch=getchar();
		if(ch<'0'||ch>'9'){if(ch=='-')mark=-1;ch=getchar();}
		while(ch>='0'&&ch<='9')
			num=(num<<3)+(num<<1)+ll(ch-'0'),ch=getchar();
		return num*mark;
	}
	void qwrite(ll num){
		char stack[25];ll len=0;if(num<0){putchar('-');num=-num;}
		if(!num)stack[++len]='0';
		while(num)stack[++len]=char(num%10+'0'),num=num/10;
		for(int i=len;i>=1;i--)putchar(stack[i]);putchar(' ');
	}
	void qwriteln(ll num){qwrite(num);putchar('\n');}
}
#define read FastIO::qread
#define write FastIO::qwrite
#define writeln FastIO::qwriteln
//==============================

int n,q,w[100010],c[100010];
namespace remained_apple{
	int n,s,h[100010],p[200010],t[200010],de[100010],sz[100010];
	int clk,dfn[100010],fa[100010],tp[100010],son[100010];
	void adde(int a,int b){p[++s]=h[a],t[s]=b,h[a]=s;}
	void dfs1(int u,int f){
		fa[u]=f,de[u]=de[f]+1;sz[u]=1;
		for(int i=h[u];i;i=p[i]){
			int v=t[i];if(v==f)continue;
			dfs1(v,u);sz[u]+=sz[v];
			if(sz[son[u]]<sz[v])son[u]=v;
		}
	}
	void dfs2(int u,int top){
		dfn[u]=++clk;tp[u]=top;
		if(!son[u])return;dfs2(son[u],top);
		for(int i=h[u];i;i=p[i]){
			int v=t[i];if(v==fa[u]||v==son[u])continue;
			dfs2(v,v);
		}
	}
	namespace xds{
		int mx[3000010],sm[3000010];
		int lc[3000010],rc[3000010],sz,rt[100010];
		void upd(int &o,int l,int r,int p,int v){
			if(!o)o=++sz;
			//printf("upd(%d,%d,%d,%d,%d)\n",o,l,r,p,v);
			if(l==r){mx[o]=sm[o]=v;return;}
			int m=(l+r)>>1;
			if(p<=m)upd(lc[o],l,m,p,v);
			else upd(rc[o],m+1,r,p,v);
			mx[o]=max(mx[lc[o]],mx[rc[o]]);
			sm[o]=sm[lc[o]]+sm[rc[o]];
		}
		void rmv(int o,int l,int r,int p){
			if(l==r){mx[o]=sm[o]=0;return;}
			int m=(l+r)>>1;
			if(p<=m)rmv(lc[o],l,m,p);
			else rmv(rc[o],m+1,r,p);
			mx[o]=max(mx[lc[o]],mx[rc[o]]);
			sm[o]=sm[lc[o]]+sm[rc[o]];
		}
		int qsum(int o,int l,int r,int L,int R){
			//printf("qsum(%d,%d,%d,%d,%d)\n",o,l,r,L,R);
			if(L<=l&&r<=R)return sm[o];
			int m=(l+r)>>1,ans=0;
			if(L<=m)ans=qsum(lc[o],l,m,L,R);
			if(R>m)ans+=qsum(rc[o],m+1,r,L,R);
			return ans;
		}
		int qmax(int o,int l,int r,int L,int R){
			if(L<=l&&r<=R)return mx[o];
			int m=(l+r)>>1,ans=0;
			if(L<=m)ans=qmax(lc[o],l,m,L,R);
			if(R>m) ans=max(ans,qmax(rc[o],m+1,r,L,R));
			return ans;
		}
	}
	using namespace xds;
	void CC(int x,int tc){rmv(rt[c[x]],1,n,dfn[x]);upd(rt[tc],1,n,dfn[x],w[x]);c[x]=tc;}
	void CW(int x,int tw){upd(rt[c[x]],1,n,dfn[x],tw);w[x]=tw;}
	int QS(int x,int y){
		int sum=0,tmp=c[x];
		while(tp[x]!=tp[y]){
			if(de[tp[x]]<de[tp[y]])swap(x,y);
			sum+=qsum(rt[tmp],1,n,dfn[tp[x]],dfn[x]);
			x=fa[tp[x]];//write(x);writeln(y);
		}
		if(de[x]<de[y])swap(x,y);
		return sum+qsum(rt[tmp],1,n,dfn[y],dfn[x]);
	}
	int QM(int x,int y){
		int maxx=0,tmp=c[x];
		while(tp[x]!=tp[y]){
			if(de[tp[x]]<de[tp[y]])swap(x,y);
			maxx=max(maxx,qmax(rt[tmp],1,n,dfn[tp[x]],dfn[x]));
			x=fa[tp[x]];
		}
		if(de[x]<de[y])swap(x,y);
		return max(maxx,qmax(rt[tmp],1,n,dfn[y],dfn[x]));
	}
	int mian(){//interesting
		char S[5];
		n=read(),q=read();
		for(int i=1;i<=n;i++)w[i]=read(),c[i]=read();
		for(int i=1;i<=n-1;i++){
			int a=read(),b=read();
			adde(a,b);adde(b,a);
		}
		dfs1(1,0);dfs2(1,1);
		for(int i=1;i<=n;i++)upd(rt[c[i]],1,n,dfn[i],w[i]);
		while(q--){
			scanf("%s",S+1);int a=read(),b=read();
			switch(S[2]){
				case 'C':CC(a,b);break;
				case 'W':CW(a,b);break;
				case 'S':writeln(QS(a,b));break;
				case 'M':writeln(QM(a,b));break;
			}
		}
		return 1004535809;
	}
}
signed main(){return remained_apple::mian()-1004535809;}