#include <stdio.h>
#include <string.h>
#define RG register
#define N 100010
#define dmax(a,b) ((a)>(b)?(a):(b))
template<class Type> inline void R(RG Type &x) {
RG int c=getchar();for(;c<48||c>57;c=getchar());
for(x=0;c>47&&c<58;x=(x<<1)+(x<<3)+c-48,c=getchar()); }
bool vis[N];int n,q,w[N],c[N],tim,fa[N],dep[N],sz[N],lef[N],top[N],hso[N],tot,root[N];
struct Pt {
int v; Pt *nt; }*fi[N],me[N<<1],*tp=me;
struct Ch {
int ls,rs,mx,su; }tr[N*40];
inline void link(RG int x,RG int y) {
*++tp=(Pt){y,fi[x]},fi[x]=tp;
*++tp=(Pt){x,fi[y]},fi[y]=tp; }
void dfsi(RG int x){
vis[x]=sz[x]=1;
for(RG Pt *it=fi[x];it;it=it->nt)
if(!vis[it->v])
dep[it->v]=dep[x]+1,
fa[it->v]=x,
dfsi(it->v),
sz[x]+=sz[it->v],
hso[x]=sz[it->v]>sz[hso[x]]?it->v:hso[x];
}
void dfsm(RG int x){
vis[x]=0;
top[x]=x==hso[fa[x]]?top[fa[x]]:x;
lef[x]=++tim;
if(hso[x]){
dfsm(hso[x]);
for(RG Pt *it=fi[x];it;it=it->nt)
if(vis[it->v])
dfsm(it->v);
}
}
inline int lca(RG int x,RG int y){
while(top[x]^top[y])
dep[top[x]]>dep[top[y]]?
x=fa[top[x]]:
y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
inline void Pu(RG int pr) {
tr[pr].mx=dmax(tr[tr[pr].ls].mx,tr[tr[pr].rs].mx);
tr[pr].su=tr[tr[pr].ls].su+tr[tr[pr].rs].su; }
void modify(RG int &pr,RG int x,RG int y,RG int po,RG int nu){
if(!pr)pr=++tot;
if(!(x^y)) {tr[pr].mx=tr[pr].su=nu; return; }
RG int mid=x+y>>1;
if(po<=mid)modify(tr[pr].ls,x,mid,po,nu);
else modify(tr[pr].rs,mid+1,y,po,nu);
Pu(pr);
}
int qmx(RG int pr,RG int x,RG int y,RG int u,RG int v){
if(!pr)return 0;
if(x==u&&y==v)return tr[pr].mx;
RG int mid=x+y>>1;
if(v<=mid)return qmx(tr[pr].ls,x,mid,u,v);
if(u>mid)return qmx(tr[pr].rs,mid+1,y,u,v);
return dmax(qmx(tr[pr].ls,x,mid,u,mid),qmx(tr[pr].rs,mid+1,y,mid+1,v));
}
int qsm(RG int pr,RG int x,RG int y,RG int u,RG int v){
if(!pr)return 0;
if(x==u&&y==v)return tr[pr].su;
RG int mid=x+y>>1;
if(v<=mid)return qsm(tr[pr].ls,x,mid,u,v);
if(u>mid)return qsm(tr[pr].rs,mid+1,y,u,v);
return qsm(tr[pr].ls,x,mid,u,mid)+qsm(tr[pr].rs,mid+1,y,mid+1,v);
}
inline int solvem(RG int col,RG int x,RG int f){
int re=0;
while(top[x]^top[f])
re=dmax(re,qmx(root[col],1,n,lef[top[x]],lef[x])),x=fa[top[x]];
re=dmax(re,qmx(root[col],1,n,lef[f],lef[x]));
return re;
}
inline int solves(int col,int x,int f){
int re=0;
while(top[x]^top[f])
re+=qsm(root[col],1,n,lef[top[x]],lef[x]),x=fa[top[x]];
re+=qsm(root[col],1,n,lef[f],lef[x]);
return re;
}
int main(){
RG char si[10];R(n),R(q);
for(RG int i=1;i<=n;i++)R(w[i]),R(c[i]);
for(RG int i=1,x,y;i<n;i++)R(x),R(y),link(x,y);
dfsi(1),dfsm(1);
for(RG int i=1;i<=n;i++)modify(root[c[i]],1,n,lef[i],w[i]);
for(int x,y,t,tmp;q;q--){
scanf("%s",si),R(x),R(y);
if(si[0]==‘C‘&&si[1]==‘C‘)
modify(root[c[x]],1,n,lef[x],0),
c[x]=y,
modify(root[c[x]],1,n,lef[x],w[x]);
if(si[0]==‘C‘&&si[1]==‘W‘)
modify(root[c[x]],1,n,lef[x],y),w[x]=y;
if(si[0]==‘Q‘&&si[1]==‘S‘)
t=lca(x,y),tmp=solves(c[x],x,t)+solves(c[x],y,t),c[x]==c[t]?tmp-=w[t]:1,printf("%d\n",tmp);
if(si[0]==‘Q‘&&si[1]==‘M‘)
t=lca(x,y),printf("%d\n",dmax(solvem(c[x],x,t),solvem(c[x],y,t)));
}
return 0;
}
