#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=1e5+5,K=1e3+5,M=2e5+5,INF=2e18;
int n,m,tot,cnt,len;
int head[N],e[M],nxt[M],_col[N],_w[N],col[N],w[N],siz[N],son[N],top[N],id[N],dep[N],fa[N],lp[K],rp[K],loc[N];
int sum[N][K],maxn[N][K];
void add(int u,int v){
	e[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
void dfs1(int u,int f){
	fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
	for(int i=head[u];i;i=nxt[i]){
		int v=e[i];
		if(v==f) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int tp){
	top[u]=tp,id[u]=++cnt,w[cnt]=_w[u],col[cnt]=_col[u];
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){
		int v=e[i];
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
int querysum(int c,int l,int r){
	int lc=loc[l],rc=loc[r],ans=0;
	if(lc==rc){
		for(int i=l;i<=r;i++) if(col[i]==c) ans+=w[i];
		return ans;
	}
	int x=l,y=r;
	for(;int(x/len)==lc;x++) if(col[x]==c) ans+=w[x];
	for(;int(y/len)==rc;y--) if(col[y]==c) ans+=w[y];
	for(int k=int(x/len);k<=int(y/len);k++) ans+=sum[c][k];
	return ans;
}
int querymax(int c,int l,int r){
	int lc=loc[l],rc=loc[r],ans=-INF;
	if(lc==rc){
		for(int i=l;i<=r;i++) if(col[i]==c) ans=max(ans,w[i]);
		return ans;
	}
	int x=l,y=r;
	for(;int(x/len)==lc;x++) if(col[x]==c) ans=max(ans,w[x]);
	for(;int(y/len)==rc;y--) if(col[y]==c) ans=max(ans,w[y]);
	for(int k=int(x/len);k<=int(y/len);k++) ans=max(ans,maxn[c][k]);
	return ans;
}
void updatecol(int u,int c){
	int lst=col[u],k=loc[u];
	col[u]=c,maxn[lst][k]=maxn[c][k]=-INF,sum[lst][k]=sum[c][k]=0;
	for(int i=lp[k];i<=rp[k];i++){
		if(col[i]==lst) maxn[lst][k]=max(maxn[lst][k],w[i]),sum[lst][k]+=w[i];
		if(col[i]==c) maxn[c][k]=max(maxn[c][k],w[i]),sum[c][k]+=w[i];
	}
}
void updatew(int u,int c){
	int k=loc[u];
	w[u]=c,maxn[col[u]][k]=-INF,sum[col[u]][k]=0;
	for(int i=lp[k];i<=rp[k];i++) sum[col[u]][k]+=w[i],maxn[col[u]][k]=max(maxn[col[u]][k],w[i]);
}
int qs(int c,int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans+=querysum(c,id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	ans+=querysum(c,id[v],id[u]);
	return ans;
}
int qm(int c,int u,int v){
	int ans=-INF;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans=max(ans,querymax(c,id[top[u]],id[u]));
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ans=max(ans,querymax(c,id[u],id[v]));
	return ans;
}
signed main(){
	n=read(),m=read();
	len=sqrt(double(n/log2(n)));
	for(int i=1;i<=n;i++) _w[i]=read(),_col[i]=read();
	for(int i=1;i<n;i++){
		int u,v;
		u=read(),v=read();
		add(u,v),add(v,u);
	}
	dfs1(1,-1),dfs2(1,1);
	memset(lp,0x3f,sizeof lp),memset(rp,-0x3f,sizeof rp);
	for(int i=1;i<=n;i++){
		int k=i/len;
		loc[i]=k;
		lp[k]=min(lp[k],i),rp[k]=max(rp[k],i);
		sum[col[i]][k]+=w[i];
		maxn[col[i]][k]=max(maxn[col[i]][k],w[i]);
	}
	for(int i=1;i<=m;i++){
		string op;
		int x,y;
		cin>>op,x=read(),y=read();
		if(op=="CW") updatew(id[x],y);
		else if(op=="CC") updatecol(id[x],y);
		else if(op=="QS") cout<<qs(col[id[x]],x,y)<<endl;
		else if(op=="QM") cout<<qm(col[id[x]],x,y)<<endl;
	}
	return 0;
}