rt

#include<cstdio>
#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 10;
int n, q, cnt, num;
int head[MAXN], rel[MAXN], val[MAXN];
int fa[MAXN], size[MAXN], deep[MAXN];
int dfn[MAXN], son[MAXN], top[MAXN];

struct Edge{
    int to, next;
}e[MAXN << 1];

inline void Add(int u, int v){
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

struct Segment_Tree{
    int tot;
    int root[MAXN];

    struct Tree{
        int lson, rson;
        int max, sum;

        Tree(){
            lson = rson = 0;
            max = sum = 0;
        }
    }tr[MAXN * 25];

    Segment_Tree(){
        tot = 0;
    }

    #define lson(x) tr[x].lson
    #define rson(x) tr[x].rson

    inline void Pushup(int rt){
        tr[rt].sum = tr[lson(rt)].sum + tr[rson(rt)].sum;
        tr[rt].max = max(tr[lson(rt)].max, tr[rson(rt)].max);
    }

    void Update(int &rt, int pos, int data, int L, int R){
        if(!rt) rt = ++tot;

        if(L == R){
            tr[rt].sum = data;
            tr[rt].max = data;
            return;
        }

        int mid = (L + R) >> 1;
        if(pos <= mid) Update(lson(rt), pos, data, L, mid);
        else Update(rson(rt), pos, data, mid + 1, R);

        Pushup(rt);
    }

    void Delete(int rt, int pos, int L, int R){
        if(!rt) return;

        if(L == R){
            tr[rt].sum = 0;
            tr[rt].max = 0;
            return;
        }

        int mid = (L + R) >> 1;
        if(pos <= mid) Delete(lson(rt), pos, L, mid);
        else Delete(rson(rt), pos, mid + 1, R);

        Pushup(rt);
    }

    int Query_Sum(int rt, int l, int r, int L, int R){
        if(!rt) return 0;

        if(l <= L && r >= R)
            return tr[rt].sum;

        int mid = (L + R) >> 1;
        if(r <= mid) return Query_Sum(lson(rt), l, r, L, mid);
        else if(l > mid) return Query_Sum(rson(rt), l, r, mid + 1, R);
        else return Query_Sum(lson(rt), l, r, L, mid) + Query_Sum(rson(rt), l, r, mid + 1, R);
    }

    int Query_Max(int rt, int l, int r, int L, int R){
        if(!rt) return 0;

        if(l <= L && r >= R)
            return tr[rt].max;
        
        int mid = (L + R) >> 1;
        if(r <= mid) return Query_Max(lson(rt), l, r, L, mid);
        else if(l > mid) return Query_Max(rson(rt), l, r, mid + 1, R);
        else return max(Query_Max(lson(rt), l, r, L, mid), Query_Max(rson(rt), l, r, mid + 1, R));
    }
}S;

void dfs_deep(int rt, int father, int depth){
    size[rt] = 1;
    fa[rt] = father;
    deep[rt] = depth;

    int max_son = -1;
    for(register int i = head[rt]; i; i = e[i].next){
        int v = e[i].to;
        if(v == father) continue;

        dfs_deep(v, rt, depth + 1);
        size[rt] += size[v];

        if(size[v] > max_son){
            son[rt] = v;
            max_son = size[v];
        }
    }
}

void dfs_top(int rt, int top_fa){
    dfn[rt] = ++num;
    top[rt] = top_fa;

    if(!son[rt]) return;
    dfs_top(son[rt], top_fa);

    for(register int i = head[rt]; i; i = e[i].next){
        int v = e[i].to;

        if(!dfn[v]) dfs_top(v, v);
    }
}

int Query_Sum_Tree(int x, int y, int opt){
    int ans = 0;

    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        ans += S.Query_Sum(S.root[opt], dfn[top[x]], dfn[x], 1, n);
        x = fa[top[x]];
    }

    if(deep[x] > deep[y]) swap(x, y);
    ans += S.Query_Sum(S.root[opt], dfn[x], dfn[y], 1, n);

    return ans;
}

int Query_Max_Tree(int x, int y, int opt){
    int ans = -1;

    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        ans+= max(ans, S.Query_Max(S.root[opt], dfn[top[x]], dfn[x], 1, n));
        x = fa[top[x]];
    }

    if(deep[x] > deep[y]) swap(x, y);
    ans = max(ans, S.Query_Max(S.root[opt], dfn[x], dfn[y], 1, n));

    return ans;
}

inline int read(){
    int x = 0, f = 1;
    char c = getchar();

    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }

    return x * f;
}

int main(){
    n = read(), q = read();
    for(register int i = 1; i <= n; i++){
        val[i] = read();
        rel[i] = read();
    }
    for(register int i = 1; i <= n - 1; i++){
        int u, v;
        u = read(), v = read();
        Add(u, v);
        Add(v, u);
    }

    dfs_deep(1, 0, 1);
    dfs_top(1, 1);    
    for(register int i = 1; i <= n; i++)
        S.Update(S.root[rel[i]], dfn[i], val[i], 1, n);

    for(register int i = 1; i <= q; i++){
        char opt[5];
        scanf("%s", opt + 1);

        if(opt[1] == 'C' && opt[2] == 'C'){
            int x, c;
            x = read(), c = read();

            S.Delete(S.root[rel[x]], dfn[x], 1, n);
            rel[x] = c;
            S.Update(S.root[rel[x]], dfn[x], val[i], 1, n);
        }
        else if(opt[1] == 'C' && opt[2] == 'W'){
            int x, w;
            x = read(), w = read();

            val[x] = w;
            S.Update(S.root[rel[x]], dfn[x], w, 1, n);
        }
        else if(opt[1] == 'Q' && opt[2] == 'S'){
            int x, y;
            x = read(), y = read();

            printf("%d\n", Query_Sum_Tree(x, y, rel[x]));
        }
        else if(opt[1] == 'Q' && opt[2] == 'M'){
            int x, y;
            x = read(), y = read();

            printf("%d\n", Query_Max_Tree(x, y, rel[x]));
        }
    } 

    return 0;
}