命題

給定一棵有n個節點的無根樹和m個操作，操作有2類：
1. 將節點a到節點b路徑上所有點都染成顏色c。
2. 詢問節點a到節點b路徑上的顏色段數量（連續相同顏色被認為是同一段）。

---

類比序列上的顏色段問題，直接套用樹鏈剖分解決即可，需要注意鏈與鏈之間還要進行判斷，實現技巧可以參考下面的代碼第130行的query函數。

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
 
const int N = 1e5 + 5;
 
struct Query {
    int op, a, b, c;
    Query() {}
    Query(int op, int a, int b) : op(op), a(a), b(b) {}
    Query(int op, int a, int b, int c) : op(op), a(a), b(b), c(c) {}
} Q[N];
 
int n, q, _N, hd[N], nxt[2 * N], to[2 * N], w[2 * N], tot, mark;
int s[N], dep[N], f[N], df[N], u_son[N], fa[N], top[N];
int tr[8 * N], lc[8 * N], rc[8 * N], tag[8 * N];
int A[N], B[N], F[N];
 
void up(int p) {
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
    if (rc[p << 1] == lc[p << 1 | 1]) tr[p]--;
    lc[p] = lc[p << 1];
    rc[p] = rc[p << 1 | 1];
}
 
void down(int p) {
    if (tag[p]) {
        tag[p << 1] = tag[p << 1 | 1] = tag[p];
        lc[p << 1] = rc[p << 1] = tag[p];
        lc[p << 1 | 1] = rc[p << 1 | 1] = tag[p << 1 | 1];
        tr[p << 1] = tr[p << 1 | 1] = 1;
        tag[p] = 0;
    }
}
 
void build(int l, int r, int p) {
    if (l == r) {
        tr[p] = 1;
        lc[p] = rc[p] = A[df[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    up(p);
}
 
void update(int l, int r, int L, int R, int x, int p) {
    if (L <= l && r <= R) {
        tag[p] = x;
        lc[p] = rc[p] = x;
        tr[p] = 1;
        return;
    }
    down(p);
    int mid = (l + r) / 2;
    if (L <= mid) update(l, mid, L, R, x, p << 1);
    if (R > mid) update(mid + 1, r, L, R, x, p << 1 | 1);
    up(p);
}
 
int lst;
int query(int l, int r, int L, int R, int p) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) {
        assert(lc[p] != 0);
        int ret = tr[p] - (lst == lc[p]);
        lst = rc[p];
        return ret;
    }
    down(p);
    int mid = (l + r) / 2;
    return query(l, mid, L, R, p << 1) + query(mid + 1, r, L, R, p << 1 | 1);
}
 
int get(int l, int r, int id, int p) {
    if (l == r) return lc[p];
    int mid = (l + r) / 2;
    down(p);
    if (id <= mid) return get(l, mid, id, p << 1);
    else return get(mid + 1, r, id, p << 1 | 1);
}
 
 
void add(int a, int b) {
    nxt[++tot] = hd[a], to[hd[a] = tot] = b;
    nxt[++tot] = hd[b], to[hd[b] = tot] = a;
}
 
void dfs1(int u, int _fa, int _dep) {
    fa[u] = _fa;
    dep[u] = _dep;
    s[u] = 1;
    for (int e = hd[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v != _fa) {
            dfs1(v, u, _dep + 1);
            s[u] += s[v];
            if (!u_son[u] || s[v] > s[u_son[u]]) u_son[u] = v;
        }
    }
}
 
void dfs2(int u, int id) {
    top[u] = id;
    f[u] = ++mark;
    df[mark] = u;
    if (!u_son[u]) return;
    dfs2(u_son[u], id);
    for (int e = hd[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v != u_son[u] && v != fa[u]) dfs2(v, v);
    }
}
 
void update(int a, int b, int c) {
    for (; top[a] != top[b]; b = fa[top[b]]) {
        if (dep[top[b]] < dep[top[a]]) swap(a, b);
        update(1, mark, f[top[b]], f[b], c, 1);
    }
    if (dep[b] < dep[a]) swap(a, b);
    update(1, mark, f[a], f[b], c, 1);
}
 
int Lst[2], cur, ans;
 
void query(int a, int b) {
    cur = Lst[0] = Lst[1] = ans = 0;
    for (; top[a] != top[b]; b = fa[top[b]]) {
        if (dep[top[b]] < dep[top[a]]) swap(a, b), cur ^= 1;
        lst = 0, ans += query(1, mark, f[top[b]], f[b], 1);
        if (get(1, mark, f[b], 1) == Lst[cur ^ 1]) ans--;
        Lst[cur ^ 1] = get(1, mark, f[top[b]], 1);
    }
    if (dep[b] <= dep[a]) swap(a, b), cur ^= 1;
    int tmp;
    lst = 0, ans += (tmp = query(1, mark, f[a], f[b], 1));
    int V = get(1, mark, f[a], 1);
    int W = get(1, mark, f[b], 1);
    int Y = Lst[cur ^ 1];
    int Z = Lst[cur];
    if (Z == V) ans--;
    if (Y == W) ans--;
    printf("%d\n", ans);
}
 
void discretization() {
    sort(B + 1, B + _N + 1);
    _N = unique(B + 1, B + _N + 1) - B;
    for (int i = 1; i <= n; i++) {
        int _F = lower_bound(B + 1, B + _N + 1, A[i]) - B;
        F[_F] = A[i];
        A[i] = _F;
    }
    for (int i = 1; i <= q; i++) {
        if (Q[i].op == 0) {
            int _F = lower_bound(B + 1, B + _N + 1, Q[i].c) - B;
            F[_F] = Q[i].c;
            Q[i].c = _F;
        }
    }
}
 
int main() {
    scanf("%d%d", &n, &q);
    _N = n;
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]), B[i] = A[i];
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    for (int i = 1; i <= q; i++) {
        char op[5];
        int a, b, c;
        scanf("%s", op);
        if (op[0] == 'C') scanf("%d%d%d", &a, &b, &c), Q[i] = Query(0, a, b, c), B[++_N] = c;
        if (op[0] == 'Q') scanf("%d%d", &a, &b), Q[i] = Query(1, a, b);
    }
    discretization();
    build(1, mark, 1);
    for (int i = 1; i <= q; i++) {
        Query &X = Q[i];
        if (X.op == 0) update(X.a, X.b, X.c);
        if (X.op == 1) query(X.a, X.b);
    }
    return 0;
}
Code language: PHP (php)