对拍拍不出来 RE 求调，重链剖分，分块。

#include<bits/stdc++.h>
#define ll int
#define fir first
#define sec second
using namespace std;

vector<ll>eg[100005];
pair<ll,ll>cpo[100005];

ll n,Q,B,lit,inb[100005];
ll dep[100005],siz[100005];
ll son[100005],fas[100005];

void dfs_1(ll fa,ll p){
	dep[p]=dep[fa]+1;
	siz[p]=1;fas[p]=fa;
	for(ll v:eg[p]){
		if(v==fa)continue;
		dfs_1(p,v);
		siz[p]+=siz[v];
		if(siz[son[p]]<siz[v])son[p]=v;
	}
}

struct PIC{
	ll L,R,sm[100005],mx[100005];
	PIC(){
		memset(sm,0,sizeof(sm));
		memset(mx,0,sizeof(mx));
	}
};
struct BLK{
	ll op,len,top;
	vector<PIC>hac;
	vector<ll>pot={0},inw={0};
	void init(){
		if(pot.size()<B)op=0;
		else{
			ll p=0;
			op=1;len=pot.size()-1;
			while(1){
				PIC add;
				add.L=p+1,add.R=min(len,p+B);
//				cout<<"add.L = "<<add.L<<"   add.R = "<<add.R<<endl;
				for(ll i=add.L;i<=add.R;i++){
//					cout<<"i = "<<i<<"   pot[i] = "<<pot[i]<<"   {"<<cpo[pot[i]].fir<<","<<cpo[pot[i]].sec<<"}"<<endl;
					inw[pot[i]]=hac.size();
					add.sm[cpo[pot[i]].sec]+=cpo[pot[i]].fir;
					add.mx[cpo[pot[i]].sec]=max(add.mx[cpo[pot[i]].sec],cpo[pot[i]].fir);
				}
				hac.push_back(add);
				p=add.R;
				if(add.R==len)break;
			}
		}
	}
	inline void era(ll k){
		for(ll i=hac[k].L;i<=hac[k].R;i++){
			hac[k].sm[cpo[pot[i]].sec]=0;
			hac[k].mx[cpo[pot[i]].sec]=0;
		}
	}
	inline void add(ll k){
//		cout<<"add("<<k<<")"<<endl;
		for(ll i=hac[k].L;i<=hac[k].R;i++){
			hac[k].sm[cpo[pot[i]].sec]+=cpo[pot[i]].fir;
			hac[k].mx[cpo[pot[i]].sec]=max(hac[k].mx[cpo[pot[i]].sec],cpo[pot[i]].fir);
//			cout<<"hac["<<k<<"].sm["<<cpo[pot[i]].sec<<"] += "<<cpo[pot[i]].fir<<" = "<<hac[k].sm[cpo[pot[i]].sec]<<endl;
//			cout<<"hac["<<k<<"].mx["<<cpo[pot[i]].sec<<"] = max( "<<cpo[pot[i]].fir<<" ) = "<<hac[k].mx[cpo[pot[i]].sec]<<endl;
		}
	}
	inline void modify_1(ll p,ll k){
		if(op==1){
			era(inw[p]);
			cpo[p].fir=k;
			add(inw[p]);
		}
		else cpo[p].fir=k;
	}
	inline void modify_2(ll p,ll k){
		if(op==1){
			era(inw[p]);
			cpo[p].sec=k;
			add(inw[p]);
		}
		else cpo[p].sec=k;
	}
	inline ll pos(ll k){return lower_bound(pot.begin(),pot.end(),k)-pot.begin();}
	inline ll query_1(ll x,ll y,ll k){
		x=pos(x),y=pos(y);
		if(x>y)swap(x,y);
		ll res=0;
		if(op==1){
			for(PIC &it:hac){
				if(it.L>=x&&it.R<=y)res+=it.sm[k];
				else{
					for(ll i=it.L;i<=it.R;i++)
						if(cpo[pot[i]].sec==k)
							res+=cpo[pot[i]].fir;
				}
			}
		}
		else{
			for(ll i=x;i<=y;i++)
				if(cpo[pot[i]].sec==k)
					res+=cpo[pot[i]].fir;
		}
		return res;
	}
	inline ll query_2(ll x,ll y,ll k){
		x=pos(x),y=pos(y);
		if(x>y)swap(x,y);
		ll res=0;
		if(op==1){
			for(PIC &it:hac){
				if(it.L>=x&&it.R<=y)res=max(res,it.mx[k]);
				else{
					for(ll i=it.L;i<=it.R;i++)
						if(cpo[pot[i]].sec==k)
							res=max(res,cpo[pot[i]].fir);
				}
			}
		}
		else{
			for(ll i=x;i<=y;i++)
				if(cpo[pot[i]].sec==k)
					res=max(res,cpo[pot[i]].fir);
		}
		return res;
	}
}blk[100005];

void dfs_2(ll p,ll opt){
	inb[p]=opt;
	blk[opt].pot.push_back(p);
	if(son[p])dfs_2(son[p],opt);
	for(ll v:eg[p]){
		if(v==fas[p]||v==son[p])continue;
		blk[++lit].top=v;
		dfs_2(v,lit);
	}
}

inline ll query_1(ll x,ll y,ll k){
	ll res=0;
	while(inb[x]!=inb[y]){
		if(dep[blk[inb[x]].top]<dep[blk[inb[y]].top])swap(x,y);
		res+=blk[inb[x]].query_1(blk[inb[x]].top,x,k);
		x=fas[blk[inb[x]].top];
	}
	if(dep[x]>dep[y])swap(x,y);
	res+=blk[inb[x]].query_1(x,y,k);
	return res;
}
inline ll query_2(ll x,ll y,ll k){
	ll res=0;
	while(inb[x]!=inb[y]){
		if(dep[blk[inb[x]].top]<dep[blk[inb[y]].top])swap(x,y);
		res=max(res,blk[inb[x]].query_2(blk[inb[x]].top,x,k));
		x=fas[blk[inb[x]].top];
	}
	if(dep[x]>dep[y])swap(x,y);
	res=max(res,blk[inb[x]].query_2(x,y,k));
	return res;
}

signed main(){
//	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
//	ios::sync_with_stdio(false);
	
	cin>>n>>Q;B=sqrt(n);
	for(ll i=1;i<=n;i++)
		cin>>cpo[i].fir>>cpo[i].sec;
	for(ll i=1;i<n;i++){
		ll x,y;cin>>x>>y;
		eg[x].push_back(y);
		eg[y].push_back(x);
	}
		
	dfs_1(0,1);
	
	blk[++lit].top=1;
	dfs_2(1,lit);
	
//	cout<<"inb : ";for(ll i=1;i<=n;i++)cout<<inb[i]<<" ";cout<<endl;
	
//	cout<<"init"<<endl;
	for(ll i=1;i<=lit;i++){
//		cout<<endl<<"i = "<<i<<endl;
//		cout<<"pot : ";for(ll it:blk[i].pot)cout<<it<<" ";cout<<endl;
		blk[i].init();
//		cout<<"op = "<<blk[i].op<<"   blk[i].hac.size() = "<<blk[i].hac.size()<<endl;
//		if(blk[i].op==1){
//			cout<<"hac : "<<endl;
//			for(PIC &it:blk[i].hac){
//				cout<<"L = "<<it.L<<"   R = "<<it.R<<endl;
//				cout<<"sm : ";for(ll q=1;q<=5;q++)cout<<it.sm[q]<<" ";cout<<endl;
//				cout<<"mx : ";for(ll q=1;q<=5;q++)cout<<it.mx[q]<<" ";cout<<endl;
//			}
//		}
	}
	
	while(Q--){
		char op;ll x,y;
		cin>>op>>op>>x>>y;
		if(op=='C')blk[inb[x]].modify_2(x,y);
		if(op=='W')blk[inb[x]].modify_1(x,y);
		if(op=='S')cout<<query_1(x,y,cpo[x].sec)<<endl;
		if(op=='M')cout<<query_2(x,y,cpo[x].sec)<<endl;
		
//		cout<<"print ==========================="<<endl;
//		for(ll i=1;i<=lit;i++){
//			cout<<endl<<"i = "<<i<<endl;
//			cout<<"pot : ";for(ll it:blk[i].pot)cout<<it<<" ";cout<<endl;
//			cout<<"op = "<<blk[i].op<<"   blk[i].hac.size() = "<<blk[i].hac.size()<<endl;
//			if(blk[i].op==1){
//				cout<<"hac : "<<endl;
//				for(PIC &it:blk[i].hac){
//					cout<<"L = "<<it.L<<"   R = "<<it.R<<endl;
//					cout<<"sm : ";for(ll q=1;q<=5;q++)cout<<it.sm[q]<<" ";cout<<endl;
//					cout<<"mx : ";for(ll q=1;q<=5;q++)cout<<it.mx[q]<<" ";cout<<endl;
//				}
//			}
//		}
		
	}
	
	return 0;
}
/*
9 1
3 1
3 2
2 1
2 3
1 3
2 1
3 2
3 1
2 1
1 2
2 3
3 4
4 5
5 6
2 7
3 8
4 9
QS 2 7
*/

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 100010
using namespace std;
int n,m,d=1,e=1,g=1;
int c[MAXN],w[MAXN],root[MAXN];
int head[MAXN],id[MAXN],top[MAXN],deep[MAXN],fa[MAXN],son[MAXN],num[MAXN];
struct node1{//结构体前向星
    int next,to;
}a[MAXN<<1];
struct node2{//动态线段树
    int l,r,data1,data2;
}b[MAXN*20];
inline int read(){//弱弱的读优
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline int max(const int &x,const int &y){//手写 max ,感觉有点手残。。。
    if(x>y)return x;
    return y;
}
void pushup(int rt){//上传
    b[rt].data1=b[b[rt].l].data1+b[b[rt].r].data1;
    b[rt].data2=max(b[b[rt].l].data2,b[b[rt].r].data2);
}
void pushdown(int rt){//清空
    b[rt].data1=b[rt].data2=b[rt].l=b[rt].r=0;
}
void insert(int k,int v,int l,int r,int &rt){//插入
    int mid;
    if(!rt)rt=e++;//如上 第3点
    if(l==v&&v==r){
        b[rt].data1=b[rt].data2=k;
        return;
    }
    mid=l+r>>1;
    if(v<=mid)insert(k,v,l,mid,b[rt].l);
    else insert(k,v,mid+1,r,b[rt].r);
    pushup(rt);
}
void remove(int k,int l,int r,int &rt){//删除
    int mid;
    if(l==r){
        pushdown(rt);
        rt=0;
        return;
    }
    mid=l+r>>1;
    if(k<=mid)remove(k,l,mid,b[rt].l);
    else remove(k,mid+1,r,b[rt].r);
    pushup(rt);
    if(!b[rt].l&&!b[rt].r){//注意这里，左子树 与 右子树 都空时，节点为空
        pushdown(rt);
        rt=0;
    }
}
int query1(int s,int t,int l,int r,int rt){//区间求和
    if(!rt)return 0;//节点为空，返回
    int mid;
    if(l==s&&r==t)
    return b[rt].data1;
    mid=l+r>>1;
    if(t<=mid)return query1(s,t,l,mid,b[rt].l);
    else if(s>mid)return query1(s,t,mid+1,r,b[rt].r);
    else return query1(s,mid,l,mid,b[rt].l)+query1(mid+1,t,mid+1,r,b[rt].r);
}
int query2(int s,int t,int l,int r,int rt){//区间求最值
    if(!rt)return 0;
    int mid;
    if(l==s&&r==t)
    return b[rt].data2;
    mid=l+r>>1;
    if(t<=mid)return query2(s,t,l,mid,b[rt].l);
    else if(s>mid)return query2(s,t,mid+1,r,b[rt].r);
    else return max(query2(s,mid,l,mid,b[rt].l),query2(mid+1,t,mid+1,r,b[rt].r));
}
void add(int x,int y){//加边
    a[d].to=y;
    a[d].next=head[x];
    head[x]=d++;
    a[d].to=x;
    a[d].next=head[y];
    head[y]=d++;
}
void buildtree(int rt){//建树+树剖准备1
    int will;
    num[rt]=1;
    for(int i=head[rt];i;i=a[i].next){
        will=a[i].to;
        if(!deep[will]){
            deep[will]=deep[rt]+1;
            fa[will]=rt;
            buildtree(will);
            num[rt]+=num[will];
            if(num[will]>num[son[rt]])son[rt]=will;
        }
    }
}
void dfs(int rt,int fa){//树剖准备2
    if(son[rt]){
        top[son[rt]]=top[rt];
        id[son[rt]]=++g;
        dfs(son[rt],rt);
    }
    int v;
    for(int i=head[rt];i;i=a[i].next){
        v=a[i].to;
        if(v==fa||v==son[rt])continue;
        top[v]=v;
        id[v]=++g;
        dfs(v,rt);
    }
}
void change1(int x,int y){//修改宗教：原宗教中删除，新宗教中插入
    remove(id[x],1,n,root[c[x]]);
    c[x]=y;
    insert(w[x],id[x],1,n,root[c[x]]);
}
void change2(int x,int y){//修改评价：直接插入
    w[x]=y;
    insert(w[x],id[x],1,n,root[c[x]]);
}
void work1(int x,int y){//求评价和
    int cs=c[x],s=0;
    while(top[x]!=top[y]){//树剖搞起
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        s+=query1(id[top[x]],id[x],1,n,root[cs]);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    s+=query1(id[x],id[y],1,n,root[cs]);//不要忘了这里。。。
    printf("%d\n",s);
}
void work2(int x,int y){//求评价最值
    int cs=c[x],s=0;
    while(top[x]!=top[y]){//同上
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        s=max(s,query2(id[top[x]],id[x],1,n,root[cs]));
        x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    s=max(s,query2(id[x],id[y],1,n,root[cs]));
    printf("%d\n",s);
}
int main(){
//	freopen("code.in","r",stdin);
//	freopen("code_2.out","w",stdout);
    int x,y;
    char ch[3];
    n=read();m=read();
    for(int i=1;i<=n;i++){w[i]=read();c[i]=read();}
    for(int i=1;i<n;i++){
        x=read();y=read();
        add(x,y);
    }
    deep[1]=id[1]=top[1]=1;//初值
    buildtree(1);
    dfs(1,0);
    for(int i=1;i<=n;i++)insert(w[i],id[i],1,n,root[c[i]]);//建初始线段树
    while(m--){//主过程
        scanf("%s",ch);x=read();y=read();
        if(ch[0]=='C'){
            if(ch[1]=='C')change1(x,y);
            if(ch[1]=='W')change2(x,y);
        }
        if(ch[0]=='Q'){
            if(ch[1]=='S')work1(x,y);
            if(ch[1]=='M')work2(x,y);
        }
    }
    return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Rand(ll x,ll y){
	return (rand()*rand())%(y-x+1)+x;
}

vector<ll>vec[100005];

signed main(){
	srand(time(0));
	freopen("code.in","w",stdout);
//	ios::sync_with_stdio(false);
	
	ll n=100000,Q=100000;
	cout<<n<<" "<<Q<<endl;
	for(ll i=1;i<=n;i++){
		ll x=Rand(1,10000),y=Rand(90000,100000);
		cout<<x<<" "<<y<<endl;
		vec[y].push_back(i);
	}
	for(ll i=1;i<=Q;i++){
		ll op=Rand(1,4);
		if(op==1)cout<<"CC "<<Rand(1,n)<<Rand(90000,100000)<<endl;
		else if(op==2)cout<<"CW "<<Rand(1,n)<<Rand(1,10000)<<endl;
		else{
			if(op==3)cout<<"QS ";
			else cout<<"QM ";
			ll p=Rand(90000,100000);
			while(vec[p].size()<2)p=Rand(90000,100000);
			cout<<vec[p][Rand(0,vec[p].size()-1)]<<" "<<vec[p][Rand(0,vec[p].size()-1)]<<endl;
		}
	}
	
	return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
signed main(){
//	ios::sync_with_stdio(false);
	ll asd=0;
	while(1){
		cout<<"第 "<<++asd<<" 次对拍"<<endl;
		system("mikker.exe");
		cout<<"after_mikker"<<endl;
		system("code.exe");
		cout<<"after_code"<<endl;
		system("code_2.exe");
		cout<<"after_code_2"<<endl;
		if(system("fc code.out code_2.out")){
			cout<<"Error!!!"<<endl;
			break;
		}
	}
//	if(system("fc code.out code_2.out"))cout<<"Error!!!";
//	else cout<<"Is OK"<<endl;
	return 0;
}