思路与算法

重链剖分将路径变成若干有方向的序列区间。每个区间保存长度、左端颜色、右端颜色和颜色段数。合并相邻非空区间时，段数为两者段数之和；如果相接处颜色相同，再减1。空区间作为合并单位元。

线段树维护上述信息，并用区间赋色懒标记处理C操作。某非空区间完全染成颜色c后，其左右颜色均为c，段数为1。

Q操作不能随意交换片段顺序：分别维护从原起点向上得到的left和通往原终点的right。起点侧取到的链段需要反转（交换左右颜色）后接到left末尾；终点侧链段按正常编号方向接到right前面。同链后按实际路径方向取中段，再合并left、中段、right。

正确性说明

每个颜色段只可能在一个区间内部，或跨过两个相邻区间的边界。边界两侧颜色不同，不发生合并；相同则恰合并一对段，因此合并公式正确。反转不改变段数，只交换两端颜色。整段赋色后的段数显然为1，故线段树能正确维护任意区间的信息。

路径拆分时，left始终按原起点到当前点的顺序保存已处理路径，right始终按当前点到原终点的顺序保存已处理路径；上行区间的反转和终点侧的前接保持此不变量。最后三部分依次组成完整原路径，按正确方向合并便得到准确的颜色段数。

复杂度

n点、m次操作。图、剖分数组和线段树数组初始化O(n)，迭代剖分及按剖分序建树O(n)。每条路径有O(log(n+1))个重链片段，每个区间查询或染色O(log(n+1))。总时间O(n+m log²(n+1))，空间O(n)。

易错点

颜色0合法，必须用-1表示没有懒标记。合并段数具有方向信息，不能仅累加各段段数，也不能忽略反转后首尾颜色互换。同点路径始终只有1段；整条路径同色也只能输出1。染色包含两个端点，最大颜色10^9仍能存入int。迭代剖分避免链形树栈溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct HLD {
    int n, tim = 0;
    vector<vector<int>> g;
    vector<int> p, d, sz, heavy, top, id, rev, order;
    HLD(int n)
        : n(n), g(n + 1), p(n + 1), d(n + 1), sz(n + 1, 1), heavy(n + 1), top(n + 1), id(n + 1),
          rev(n + 1) {
        sz[0] = 0;
    }
    void add(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void build() {
        order.push_back(1);
        for (int i = 0; i < (int)order.size(); ++i) {
            int u = order[i];
            for (int v : g[u])
                if (v != p[u])
                    p[v] = u, d[v] = d[u] + 1, order.push_back(v);
        }
        for (int i = n - 1; i > 0; --i) {
            int u = order[i], v = p[u];
            sz[v] += sz[u];
            if (sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        vector<pair<int, int>> st(1, {1, 1});
        while (!st.empty()) {
            auto q = st.back();
            st.pop_back();
            for (int u = q.first; u; u = heavy[u]) {
                top[u] = q.second;
                id[u] = ++tim;
                rev[tim] = u;
                for (int v : g[u])
                    if (p[v] == u && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
};
struct Info {
    int len, left, right, runs;
    Info(int a = 0, int b = 0, int c = 0, int d = 0) : len(a), left(b), right(c), runs(d) {
    }
};
Info mergeInfo(Info a, Info b) {
    if (!a.len)
        return b;
    if (!b.len)
        return a;
    return {a.len + b.len, a.left, b.right, a.runs + b.runs - (a.right == b.left)};
}
Info reversed(Info a) {
    swap(a.left, a.right);
    return a;
}
struct Seg {
    int n;
    vector<Info> s;
    vector<int> tag;
    Seg(vector<int> &a) : n(a.size() - 1), s(4 * n + 4), tag(4 * n + 4, -1) {
        build(1, 1, n, a);
    }
    void build(int k, int l, int r, vector<int> &a) {
        if (l == r) {
            s[k] = {1, a[l], a[l], 1};
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m, a);
        build(k * 2 + 1, m + 1, r, a);
        s[k] = mergeInfo(s[k * 2], s[k * 2 + 1]);
    }
    void put(int k, int c) {
        s[k].left = s[k].right = c;
        s[k].runs = 1;
        tag[k] = c;
    }
    void push(int k) {
        if (tag[k] < 0)
            return;
        put(k * 2, tag[k]);
        put(k * 2 + 1, tag[k]);
        tag[k] = -1;
    }
    void paint(int k, int l, int r, int a, int b, int c) {
        if (a <= l && r <= b) {
            put(k, c);
            return;
        }
        push(k);
        int m = (l + r) / 2;
        if (a <= m)
            paint(k * 2, l, m, a, b, c);
        if (b > m)
            paint(k * 2 + 1, m + 1, r, a, b, c);
        s[k] = mergeInfo(s[k * 2], s[k * 2 + 1]);
    }
    Info query(int k, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return s[k];
        push(k);
        int m = (l + r) / 2;
        Info x;
        if (a <= m)
            x = mergeInfo(x, query(k * 2, l, m, a, b));
        if (b > m)
            x = mergeInfo(x, query(k * 2 + 1, m + 1, r, a, b));
        return x;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> color(n + 1);
    for (int u = 1; u <= n; ++u)
        cin >> color[u];
    HLD h(n);
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        h.add(u, v);
    }
    h.build();
    vector<int> a(n + 1);
    for (int u = 1; u <= n; ++u)
        a[h.id[u]] = color[u];
    Seg st(a);
    while (m--) {
        char op;
        int u, v, c;
        cin >> op >> u >> v;
        if (op == 'C') {
            cin >> c;
            while (h.top[u] != h.top[v]) {
                if (h.d[h.top[u]] < h.d[h.top[v]])
                    swap(u, v);
                st.paint(1, 1, n, h.id[h.top[u]], h.id[u], c);
                u = h.p[h.top[u]];
            }
            if (h.d[u] > h.d[v])
                swap(u, v);
            st.paint(1, 1, n, h.id[u], h.id[v], c);
        } else {
            Info left, right;
            while (h.top[u] != h.top[v]) {
                if (h.d[h.top[u]] >= h.d[h.top[v]]) {
                    left = mergeInfo(left, reversed(st.query(1, 1, n, h.id[h.top[u]], h.id[u])));
                    u = h.p[h.top[u]];
                } else {
                    right = mergeInfo(st.query(1, 1, n, h.id[h.top[v]], h.id[v]), right);
                    v = h.p[h.top[v]];
                }
            }
            Info middle;
            if (h.d[u] >= h.d[v])
                middle = reversed(st.query(1, 1, n, h.id[v], h.id[u]));
            else
                middle = st.query(1, 1, n, h.id[u], h.id[v]);
            cout << mergeInfo(mergeInfo(left, middle), right).runs << '\n';
        }
    }
}