30 pts 求调QWQ

#include <bits/stdc++.h>
#define N 300005
#define PII pair <int, int>
#define int long long
const int INF = 4e18;
using namespace std;

int n, q;
vector <int> g[N];
int col[N];

int dep[N], siz[N];
int fa[N], son[N];
void dfs1(int u, int Fa) {
    dep[u] = dep[Fa] + 1;
    siz[u] = 1;
    fa[u] = Fa;
    int mxson = -1;
    for (int v : g[u]) {
        if (v == Fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (mxson < siz[v])
            mxson = siz[v], son[u] = v;
    }
}

int dfn[N], id[N], tot;
int top[N];
void dfs2(int u, int Top) {
    dfn[u] = ++tot;
    id[tot] = u;
    top[u] = Top;
    if (!son[u]) return;
    dfs2(son[u], Top);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

#define lp (p << 1)
#define rp (p << 1 | 1)
struct tree {
    int lcol, rcol;
    int sum, tag;
    tree() { lcol = rcol = sum = tag = 0; }
} t[N << 2];

tree merge(tree L, tree R) {
    if (L.sum == 0) return R;
    if (R.sum == 0) return L;
    tree ret;
    ret.lcol = L.lcol;
    ret.rcol = R.rcol;
    ret.sum = L.sum + R.sum;
    if (L.rcol == R.lcol) ret.sum--;
    return ret;
}

void pushup(int p) {
    t[p] = merge(t[lp], t[rp]);
}

void pushdown(int p) {
    if (t[p].tag == 0) return;
    t[lp].lcol = t[lp].rcol = t[p].tag;
    t[lp].sum = 1;
    t[lp].tag = t[p].tag;
    t[rp].lcol = t[rp].rcol = t[p].tag;
    t[rp].sum = 1;
    t[rp].tag = t[p].tag;
    t[p].tag = 0;
}

void build(int p, int l, int r) {
    if (l == r) {
        t[p].lcol = t[p].rcol = col[id[l]];
        t[p].sum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(lp, l, mid);
    build(rp, mid + 1, r);
    pushup(p);
}

void change(int p, int l, int r, int L, int R, int c) {
    if (L <= l && r <= R) {
        t[p].lcol = t[p].rcol = c;
        t[p].sum = 1;
        t[p].tag = c;
        return;
    }
    pushdown(p);
    int mid = (l + r) >> 1;
    if (L <= mid) change(lp, l, mid, L, R, c);
    if (mid < R) change(rp, mid + 1, r, L, R, c);
    pushup(p);
}

tree query(int p, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[p];
    pushdown(p);
    int mid = (l + r) >> 1;
    if (L <= mid && mid < R) 
        return merge(query(lp, l, mid, L, R), query(rp, mid + 1, r, L, R));
    if (L <= mid) return query(lp, l, mid, L, R);
    if (mid < R) return query(rp, mid + 1, r, L, R);
    return tree();
}

void path_col(int u, int v, int c) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        change(1, 1, n, dfn[top[u]], dfn[u], c);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    change(1, 1, n, dfn[u], dfn[v], c);
}

tree path_sum(int u, int v) {
    tree A, B; 
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) {
            tree tmp = query(1, 1, n, dfn[top[u]], dfn[u]);
            swap(tmp.lcol, tmp.rcol); 
            A = merge(tmp, A);  
            u = fa[top[u]];
        } else {
            tree tmp = query(1, 1, n, dfn[top[v]], dfn[v]);
            swap(tmp.lcol, tmp.rcol); 
            B = merge(tmp, B);  
            v = fa[top[v]];
        }
    }
    if (dep[u] >= dep[v]) {
        tree tmp = query(1, 1, n, dfn[v], dfn[u]);
        swap(tmp.lcol, tmp.rcol);  
        A = merge(tmp, A);
    } else {
        tree tmp = query(1, 1, n, dfn[u], dfn[v]);
        swap(tmp.lcol, tmp.rcol);  
        B = merge(tmp, B);
    }
    swap(B.lcol, B.rcol); 
    tree ans = merge(A, B);
    return ans;
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> col[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    while (q--) {
        char op; int u, v, c;
        cin >> op;
        if (op == 'C') {
            cin >> u >> v >> c;
            path_col(u, v, c);
        } else {
            cin >> u >> v;
            cout << path_sum(u, v).sum << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--)
        solve();
    return 0;
}