1 #include<iostream>
2 #include<cstring>
3 #include<cstdlib>
4 #include<cstdio>
5 #include<cmath>
6 #include<algorithm>
7 #define maxn 100005
8 using namespace std;
9 inline int read() {
10 int x=0,f=1;char ch=getchar();
11 for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1;
12 for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘;
13 return x*f;
14 }
15 struct data {
16 int to,next;
17 }e[maxn*2];
18 int head[maxn],cnt;
19 inline void add(int u,int v) {e[cnt].next=head[u];e[cnt].to=v;head[u]=cnt++;}
20 struct node {
21 int s[2],sum,Max;
22 }t[maxn*20];
23 int tot,size[maxn],son[maxn],f[maxn],dep[maxn],root[maxn];
24 inline void dfs(int x,int fa) {
25 size[x]=1,dep[x]=dep[fa]+1;
26 for(int i=head[x];i>=0;i=e[i].next) {
27 int to=e[i].to;if(to==fa) continue;
28 dfs(to,x);
29 size[x]+=size[to];
30 f[to]=x;
31 if(size[son[x]]<size[to]) son[x]=to;
32 }
33 }
34 int seg[maxn],rev[maxn],top[maxn],dis,now[maxn],w[maxn];
35 inline void dfs1(int x,int fa,int tp) {
36 seg[x]=++dis;rev[dis]=x;top[x]=tp;
37 if(son[x]) dfs1(son[x],x,tp);
38 for(int i=head[x];i>=0;i=e[i].next) {
39 int to=e[i].to;if(to==fa||to==son[x]) continue;
40 dfs1(to,x,to);
41 }
42 }
43 int n,q;
44 inline void pushup(int x) {
45 t[x].Max=max(t[t[x].s[0]].Max,t[t[x].s[1]].Max);
46 t[x].sum=t[t[x].s[0]].sum+t[t[x].s[1]].sum;
47 }
48 inline void update(int &x,int l,int r,int tmp,int d) {
49 if(!x) x=++tot;
50 if(l==r) {t[x].Max=t[x].sum=d;return;}
51 int mid=l+r>>1;
52 if(mid>=tmp) update(t[x].s[0],l,mid,tmp,d);
53 else update(t[x].s[1],mid+1,r,tmp,d);
54 pushup(x);
55 }
56 int _sum=0,_max=0;
57 inline void query(int x,int l,int r,int ql,int qr) {
58 if(!x) return;
59 if(ql<=l&&qr>=r) {_sum+=t[x].sum;_max=max(_max,t[x].Max);return;}
60 int mid=l+r>>1;
61 if(ql<=mid) query(t[x].s[0],l,mid,ql,qr);
62 if(qr>mid) query(t[x].s[1],mid+1,r,ql,qr);
63 }
64 inline void find(int x,int y,int z) {
65 while(top[x]!=top[y]) {
66 if(dep[top[x]]<dep[top[y]]) swap(x,y);
67 query(z,1,n,seg[top[x]],seg[x]);
68 x=f[top[x]];
69 }
70 if(dep[x]<dep[y]) swap(x,y);
71 query(z,1,n,seg[y],seg[x]);
72 }
73 int main() {
74 memset(head,-1,sizeof(head));
75 n=read(),q=read();
76 for(int i=1;i<=n;i++) {w[i]=read();now[i]=read();}
77 for(int i=1;i<n;i++) {
78 int u=read(),v=read();
79 add(u,v);add(v,u);
80 }
81 dfs(1,0);
82 dfs1(1,0,1);
83 for(int i=1;i<=n;i++) {update(root[now[i]],1,n,seg[i],w[i]);}
84 for(int i=1;i<=q;i++) {
85 char ch[3];
86 int x,y;
87 scanf("%s",ch);
88 x=read(),y=read();
89 if(ch[1]==‘C‘) {
90 update(root[now[x]],1,n,seg[x],0);
91 update(root[y],1,n,seg[x],w[x]);
92 now[x]=y;
93 }
94 else if(ch[1]==‘W‘) {
95 update(root[now[x]],1,n,seg[x],y);
96 w[x]=y;
97 }
98 else if(ch[1]==‘S‘) {
99 _sum=0;
100 find(x,y,root[now[y]]);
101 printf("%d\n",_sum);
102 }
103 else {
104 _max=0;
105 find(x,y,root[now[y]]);
106 printf("%d\n",_max);
107 }
108 }
109 }
