#include <cstdio>
#include <cstring>
#include <climits>
#include <stack>
#include <algorithm>
const int MAX_N = 100000;
const int MAX_C = 100000;
const int MAX_NODE_NUM = 3400000;
struct SegmentTree {
#define mid ((l + r) >> 1)
    struct Node {
        Node *lc, *rc;
        int sum, max;
        void init() {
            lc = rc = NULL;
            sum = max = 0;
        }
        void update() {
            sum = (lc ? lc->sum : 0) + (rc ? rc->sum : 0);
            max = std::max(lc ? lc->max : 0, rc ? rc->max : 0);
        }
    };
    static Node *newNode() {
        static Node N[MAX_NODE_NUM], *_end = N;
        return _end->init(), _end++;
    }
    Node *root;
    int L, R;
    SegmentTree(int l, int r) {
        L = l, R = r, root = NULL;
    }
    int querySum(Node *v, int l, int r, int ql, int qr) {
        if (v == NULL) return 0;
        else if (l == ql && r == qr) return v->sum;
        else if (mid >= qr) return querySum(v->lc, l, mid, ql, qr);
        else if (mid <= ql) return querySum(v->rc, mid, r, ql, qr);
        else return querySum(v->lc, l, mid, ql, mid) + querySum(v->rc, mid, r, mid, qr);
    }
    int queryMax(Node *v, int l, int r, int ql, int qr) {
        if (v == NULL) return 0;
        else if (l == ql && r == qr) return v->max;
        else if (mid >= qr) return queryMax(v->lc, l, mid, ql, qr);
        else if (mid <= ql) return queryMax(v->rc, mid, r, ql, qr);
        else return std::max(queryMax(v->lc, l, mid, ql, mid), queryMax(v->rc, mid, r, mid, qr));
    }
    void modify(Node *&v, int l, int r, int pos, int val) {
        if (v == NULL) v = newNode();
        if (r - l == 1) v->sum = v->max = val;
        else {
            if (pos < mid) modify(v->lc, l, mid, pos, val);
            else modify(v->rc, mid, r, pos, val);
            v->update();
        }
    }
    int querySum(int l, int r) {
        return querySum(root, L, R, l, r);
    }
    int queryMax(int l, int r) {
        return queryMax(root, L, R, l, r);
    }
    void modify(int pos, int val) {
        modify(root, L, R, pos, val);
    }
} *segt[MAX_C + 1];
struct Node;
struct Edge;
struct Node {
    Edge *e;
    Node *fa, *maxChild, *pathFa;
    int dfn, depth, size;
    bool vis;
    int type, val;
} N[MAX_N + 5];
struct Edge {
    Node *fr, *to;
    Edge *ne;
    Edge() {}
    Edge(Node *fr, Node *to) : fr(fr), to(to), ne(fr->e) {}
};
inline void addEdge(int fr, int to) {
    Node *u = &N[fr], *v = &N[to];
    u->e = new Edge(u, v);
    v->e = new Edge(v, u);
}
int n, c;
inline void treeChainSplit(Node *root) {
    std::stack<Node *> s;
    s.push(root), root->fa = NULL, root->depth = 0;
    while (!s.empty()) {
        Node *v = s.top();
        if (!v->vis) {
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to != v->fa) {
                    e->to->fa = v, e->to->depth = v->depth + 1;
                    s.push(e->to);
                }
            }
            v->vis = true;
        } else {
            v->size = 1, v->maxChild = NULL;
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to != v->fa) {
                    v->size += e->to->size;
                    if (!v->maxChild || v->maxChild->size < e->to->size) v->maxChild = e->to;
                }
            }
            s.pop();
        }
    }
    for (int i = 0; i < n; i++) N[i].vis = false;
    int timeStamp = 0;
    s.push(root);
    while (!s.empty()) {
        Node *v = s.top();
        if (!v->vis) {
            v->dfn = timeStamp++;
            for (Edge *e = v->e; e; e = e->ne) {
                if (e->to != v->fa && e->to != v->maxChild) {
                    s.push(e->to);
                }
            }
            if (v->maxChild) s.push(v->maxChild);
            v->pathFa = (!v->fa || v != v->fa->maxChild) ? v : v->fa->pathFa;
            v->vis = true;
        } else {
            s.pop();
        }
    }
}
inline void build() {
    treeChainSplit(N);
    for (int i = 1; i <= MAX_C; i++) segt[i] = new SegmentTree(0, n);
    for (int i = 0; i < n; i++) segt[N[i].type]->modify(N[i].dfn, N[i].val);
}
inline void modifyType(int i, int x) {
    Node *v = &N[i];
    segt[v->type]->modify(v->dfn, 0);
    segt[v->type = x]->modify(v->dfn, v->val);
}
inline void modifyVal(int i, int val) {
    Node *v = &N[i];
    segt[v->type]->modify(v->dfn, v->val = val);
}
inline int querySum(int x, int y) {
    Node *u = &N[x], *v = &N[y];
    SegmentTree *s = segt[u->type];
    int res = 0;
    while (u->pathFa != v->pathFa) {
        if (u->pathFa->depth < v->pathFa->depth) std::swap(u, v);
        res += s->querySum(u->pathFa->dfn, u->dfn + 1);
        u = u->pathFa->fa;
    }
    if (u->depth > v->depth) std::swap(u, v);
    res += s->querySum(u->dfn, v->dfn + 1);
    return res;
}
inline int queryMax(int x, int y) {
    Node *u = &N[x], *v = &N[y];
    SegmentTree *s = segt[u->type];
    int res = INT_MIN;
    while (u->pathFa != v->pathFa) {
        if (u->pathFa->depth < v->pathFa->depth) std::swap(u, v);
        res = std::max(res, s->queryMax(u->pathFa->dfn, u->dfn + 1));
        u = u->pathFa->fa;
    }
    if (u->depth > v->depth) std::swap(u, v);
    res = std::max(res, s->queryMax(u->dfn, v->dfn + 1));
    return res;
}
int main() {
    int q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &N[i].val, &N[i].type);
    }
    for (int i = 0, u, v; i < n - 1; i++) {
        scanf("%d %d", &u, &v), u--, v--;
        addEdge(u, v);
    }
    build();
    static char cmd[3];
    for (int i = 0, x, y; i < q; i++) {
        scanf("%s %d %d", cmd, &x, &y);
        if (cmd[0] == 'C') {
            x--;
            if (cmd[1] == 'C') modifyType(x, y);
            else if (cmd[1] == 'W') modifyVal(x, y);
            else throw "%%% Menci";
        } else if (cmd[0] == 'Q') {
            x--, y--;
            if (cmd[1] == 'S') printf("%d\n", querySum(x, y));
            else if (cmd[1] == 'M') printf("%d\n", queryMax(x, y));
            else throw "%%% Menci";
        } else throw "%%% Menci";
    }
    return 0;
}