树链剖分+有颜色的线段树
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
using namespace std;
const int M=4120000,N=420000;
int tot,cnt,n,m,root[N],nex[2*N],head[N],to[2*N],c[N],d[N],f[N],dep[N];
int size[N],son[N],top[N],id[N],cnt2,v1[N],v2[N],q;
struct node{int ls,rs,sum,maxn,num;node(){ls=rs=maxn=sum=0;}
}t[M];
void add(int x,int y){nex[++tot]=head[x];to[tot]=y;head[x]=tot;}
void dfs1(int x){size[x]=1;dep[x]=dep[f[x]]+1;for(int i=head[x],tmp;i;i=nex[i]){if((tmp=to[i])==f[x]) continue;f[tmp]=x;dfs1(tmp);if(size[son[x]]<size[tmp]) son[x]=tmp;size[x]+=size[tmp];}
}
void dfs2(int x,int t){top[x]=t;id[x]=++cnt2;v1[cnt2]=c[x];v2[cnt2]=d[x];if(!son[x])return;dfs2(son[x],t);for(int i=head[x];i;i=nex[i])if(!id[to[i]]) dfs2(to[i],to[i]);
}
void update(int x){t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;t[x].maxn=max(t[t[x].ls].maxn,t[t[x].rs].maxn);
}void modify(int &o,int l,int r,int id,int d){if(id>r||id<l) return ;if(!o) o=++cnt;if(l==r&&l==id){t[o].sum=t[o].maxn=d;return ;}int mid=(l+r)>>1;modify(t[o].ls,l,mid,id,d);modify(t[o].rs,mid+1,r,id,d);update(o);if(t[o].sum==0) o=0;
}
int querymax(int o,int l,int r,int ql,int qr){if(l>qr||r<ql||!o) return 0;if(l>=ql&&r<=qr) return t[o].maxn;int mid=(l+r)>>1;return max(querymax(t[o].ls,l,mid,ql,qr),querymax(t[o].rs,mid+1,r,ql,qr));
}
int querysum(int o,int l,int r,int ql,int qr){if(l>qr||r<ql||!o) return 0;if(l>=ql&&r<=qr) return t[o].sum;int mid=(l+r)>>1;return querysum(t[o].ls,l,mid,ql,qr)+querysum(t[o].rs,mid+1,r,ql,qr);
}
int get_max(int x,int y,int w){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans=max(querymax(root[c[w]],1,n,id[top[x]],id[x]),ans);x=f[top[x]];}if(dep[x]<dep[y]) swap(x,y);ans=max(querymax(root[c[w]],1,n,id[y],id[x]),ans);return ans;
}
int get_sum(int x,int y,int w){int ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans=querysum(root[c[w]],1,n,id[top[x]],id[x])+ans;x=f[top[x]];}if(dep[x]<dep[y]) swap(x,y);ans=querysum(root[c[w]],1,n,id[y],id[x])+ans;return ans;
}
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d%d",&d[i],&c[i]); for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);dfs1(1);dfs2(1,1);for(int i=1;i<=n;i++) modify(root[v1[i]],1,n,i,v2[i]);while(q--){
char s[20];cin>>s;int x,y;scanf("%d%d",&x,&y);if(s[1]=='C') modify(root[c[x]],1,n,id[x],0),c[x]=y,modify(root[c[x]],1,n,id[x],d[x]);else if(s[1]=='W') d[x]=y,modify(root[c[x]],1,n,id[x],y);else if(s[1]=='M') printf("%d\n",get_max(x,y,y));else printf("%d\n",get_sum(x,y,y));}
}