测评记录：https://www.luogu.com.cn/record/100340854

萌新调疯了，求助QAQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct edge {
    int v, next;
} e[N << 1];
ll a[N], w[N], pos[N], sum[N], L[N], R[N], tag[N], head[N], fa[N], id[N], siz[N], top[N], depth[N], son[N];
int edge_cnt, n, q, u, v, x, cnt, awa, slen;
char opt;
int qwq(int x) {
    return tag[pos[x]] ? tag[pos[x]] : a[x];
}
int qSub(int l, int r) {
    int last = 0, ans = 0;
    for (int i = l; i <= r; i ++)
        if (qwq(i) != last) last = qwq(i), ans ++;
    return ans;
}
void rebuild(int id) {
    sum[id] = qSub(L[id], R[id]);
}
void pushdown(int id) {
    if (!tag[id]) return;
    for (int i = L[id]; i <= R[id]; i ++)
        a[i] = tag[id];
    tag[id] = 0;
}
void build() {
    slen = sqrt(n), awa = n / slen + (n % slen != 0);
    for (int id = 1; id <= awa; id ++)
        L[id] = (id - 1) * slen + 1, R[id] = id * slen;
    R[awa] = n;
    for (int id = 1; id <= awa; id ++) {
        for (int j = L[id]; j <= R[id]; j ++)
            pos[j] = id;
        rebuild(id);
    }
}
void change(int l, int r, int x) {
    int lp = pos[l], rp = pos[r];
    if (lp == rp) {
        pushdown(lp);
        for (int i = l; i <= r; i ++) a[i] = x;
        rebuild(lp);
        return;
    }
    pushdown(lp), pushdown(rp);
    for (int i = l; i <= R[lp]; i ++) a[i] = x;
    for (int id = lp + 1; id < rp; id ++) tag[id] = x, sum[id] = 1;
    for (int i = L[rp]; i <= r; i ++) a[i] = x;
    rebuild(lp), rebuild(rp);
}
ll query(int l, int r) {
    int lp = pos[l], rp = pos[r];
    ll ans = 0;
    if (lp == rp) {
        return pushdown(lp), qSub(l, r);
    }
    for (int i = lp + 1; i < rp; i ++)
        ans += sum[i] - (qwq(L[i]) == qwq(R[i - 1]));
    pushdown(lp), pushdown(rp);
    return ans + qSub(l, R[lp]) + qSub(L[rp], r) - (qwq(L[rp]) == qwq(R[rp - 1]));
}
void dfs1(int u, int f, int dep) {
    fa[u] = f, siz[u] = 1, depth[u] = dep;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == f) continue;
        dfs1(v, u, dep + 1);
        if (siz[v] > siz[son[u]])
            son[u] = v;
        siz[u] += siz[v];
    }
}
void dfs2(int u, int topf) {
    id[u] = ++ cnt, a[cnt] = w[u], top[u] = topf;
    if (!son[u]) return;
    dfs2(son[u], topf);
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}
int qRange(int u, int v) {
    int ans = 0, last[2], f = 0;
    last[0] = last[1] = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v), f = !f;
        ans += query(id[top[u]], id[u]) - (qwq(id[top[u]]) == last[f]);
        last[f] = qwq(id[top[u]]), u = fa[top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v), f = !f;
    return ans + query(id[u], id[v]) - (qwq(id[u]) == last[f]) - (qwq(id[v]) == last[!f]);
}
void updRange(int u, int v, int x) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        change(id[top[u]], id[u], x), u = fa[top[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    change(id[u], id[v], x);
}
void add(int u, int v) {
    e[++ edge_cnt].v = v;
    e[edge_cnt].next = head[u];
    head[u] = edge_cnt;
}
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> w[i];
    for (int i = 1; i < n; i ++)
        cin >> u >> v, add(u, v), add(v, u);
    dfs1(1, 0, 1), dfs2(1, 1);
    build();
    for (int i = 1; i <= q; i ++) {
        cin >> opt;
        if (opt == 'C') cin >> u >> v >> x, updRange(u, v, x);
        else cin >> u >> v, cout << qRange(u, v) << '\n';
    }
    return 0;
}