「一本通 4.5 练习 3」染色

形式化题目

给定一棵包含 $n$ 个节点的树，节点从 $1$ 到 $n$ 编号，每个节点 $i$ 初始具有颜色 $c_i$ 。需要维护以下两类共 $m$ 个在线操作：

C a b c：将树上节点 $a$ 到 $b$ 简单路径上的所有点染成颜色 $c$ ；
Q a b：计算树上节点 $a$ 到 $b$ 简单路径上的颜色段数量，即路径上相邻相同颜色的连续极长节点集合构成的块数。

graph TD
    classDef red fill:#ffcccc,stroke:#ff0000,stroke-width:2px;
    classDef blue fill:#cce5ff,stroke:#004085,stroke-width:2px;
    classDef yellow fill:#fff3cd,stroke:#856404,stroke-width:2px;

    1["1 (颜色2)"]:::red
    2["2 (颜色2)"]:::red
    3["3 (颜色1)"]:::blue
    4["4 (颜色2)"]:::red
    5["5 (颜色1)"]:::yellow
    6["6 (颜色1)"]:::blue

    1 --- 2
    1 --- 3
    2 --- 4
    2 --- 5
    2 --- 6

    linkStyle 1 stroke:#ff0000,stroke-width:3px;
    linkStyle 0 stroke:#ff0000,stroke-width:3px;
    linkStyle 3 stroke:#ff0000,stroke-width:3px;

上图为样例初始状态：从节点 $3$ 到 $5$ 的路径依次经过节点 $3 \to 1 \to 2 \to 5$ 。节点颜色分别为 $1, 2, 2, 1$ ，连续相同颜色合并为一段，颜色段为 $[1], [2, 2], [1]$ ，共 $3$ 段。

正解

思路

1. 朴素方法与瓶颈

若每次操作直接在树上寻找路径并遍历：

染色操作：单次时间复杂度 $O(n)$ ；
询问操作：单次遍历路径统计相邻变色点，时间复杂度 $O(n)$ 。

当 $m, n \le 10^5$ 时，总复杂度为 $O(m \cdot n)$ ，显然会超时。需要一种支持高效处理树上路径修改与查询的数据结构。

2. 区间子问题：线段树维护连续颜色段

如果问题退化为序列（链）上的区间覆盖与连续段查询，可以用线段树维护每个区间 $[L, R]$ 的三个关键信息：

cnt：区间内的颜色段数；
lc：区间左端点（ $L$ ）的颜色；
rc：区间右端点（ $R$ ）的颜色。

在合并左子区间 $ls$ 与右子区间 $rs$ 时：

cnt = cnt_{ls} + cnt_{rs} - [rc_{ls} == lc_{rs}]

即如果左子区间的右边界颜色与右子区间的左边界颜色相同，则两段在分界点处属于同一连续段，总段数减

1

。区间覆盖通过标准 Lazy 标记维护。

3. 树上转化：树链剖分（HLD）

通过轻重链剖分，将树上每条重链映射为 DFS 序中一段连续的整数区间：

路径修改：如同常规树剖，将两点向上提升到相同重链的过程中，每次对重链对应的 DFS 序区间进行线段树区间覆盖；
路径查询与跨链合并：
- 从深度较大的链顶向上跳，查询当前重链区间 $[dfn[top[u]], dfn[u]]$ 的段数；
- 注意方向与端点： $u$ 对应区间的右端点（ $rc$ ）， $top[u]$ 对应区间的左端点（ $lc$ ）。因此自底向上跳链时，当前链的底部应当与上一段链的顶部衔接：若上一次记录的端点颜色等于当前区间的 $rc$ ，则段数减 $1$ ；
- 当两点移动到同一条重链上后，做最后一次区间查询，并将两侧分别记录的链端点颜色与最后区间的左右端点比对消重。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 18:30
# update_at: 2026-09-30 18:30

import sys
from collections.abc import Iterator

EMPTY_LAZY = -1  # 线段树区间覆盖懒标记默认空哨兵


def build_hld(
    n: int, adj: list[list[int]]
) -> tuple[list[int], list[int], list[int], list[int], list[int]]:
    """以 1 为根对无向树做轻重链剖分，返回 (parent, depth, top, dfn, rev)。"""
    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    sz = [1] * (n + 1)
    heavy = [0] * (n + 1)

    order: list[int] = []
    stack = [1]
    depth[1] = 1

    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)

    for u in reversed(order):
        p = parent[u]
        max_c = 0
        h = 0
        for v in adj[u]:
            if v != p:
                sz[u] += sz[v]
                if sz[v] > max_c:
                    max_c = sz[v]
                    h = v
        heavy[u] = h

    top = [0] * (n + 1)
    dfn = [0] * (n + 1)
    rev = [0] * (n + 1)
    timer = 0

    chain_stack = [(1, 1)]
    while chain_stack:
        u, t = chain_stack.pop()
        timer += 1
        dfn[u] = timer
        rev[timer] = u
        top[u] = t

        h = heavy[u]
        for v in adj[u]:
            if v != parent[u] and v != h:
                chain_stack.append((v, v))
        if h:
            chain_stack.append((h, t))

    return parent, depth, top, dfn, rev


def solve() -> None:
    input_data = sys.stdin.buffer.read().split()
    if not input_data:
        return
    it = iter(input_data)
    n = int(next(it))
    m = int(next(it))

    init_col = [0] + [int(next(it)) for _ in range(n)]

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = int(next(it)), int(next(it))
        adj[u].append(v)
        adj[v].append(u)

    parent, depth, top, dfn, rev = build_hld(n, adj)

    tree_cnt = [0] * (4 * n + 5)
    tree_lc = [0] * (4 * n + 5)
    tree_rc = [0] * (4 * n + 5)
    lazy = [EMPTY_LAZY] * (4 * n + 5)

    def build_seg(o: int, l: int, r: int) -> None:
        if l == r:
            c = init_col[rev[l]]
            tree_cnt[o] = 1
            tree_lc[o] = c
            tree_rc[o] = c
            return
        mid = (l + r) >> 1
        lo = o << 1
        ro = lo | 1
        build_seg(lo, l, mid)
        build_seg(ro, mid + 1, r)
        tree_cnt[o] = tree_cnt[lo] + tree_cnt[ro] - (1 if tree_rc[lo] == tree_lc[ro] else 0)
        tree_lc[o] = tree_lc[lo]
        tree_rc[o] = tree_rc[ro]

    sys.setrecursionlimit(200000)
    build_seg(1, 1, n)

    def push_down(o: int) -> None:
        c = lazy[o]
        if c != EMPTY_LAZY:
            lo = o << 1
            ro = lo | 1
            lazy[lo] = c
            tree_cnt[lo] = 1
            tree_lc[lo] = c
            tree_rc[lo] = c

            lazy[ro] = c
            tree_cnt[ro] = 1
            tree_lc[ro] = c
            tree_rc[ro] = c

            lazy[o] = EMPTY_LAZY

    def update(o: int, l: int, r: int, ql: int, qr: int, c: int) -> None:
        if ql <= l and r <= qr:
            lazy[o] = c
            tree_cnt[o] = 1
            tree_lc[o] = c
            tree_rc[o] = c
            return
        push_down(o)
        mid = (l + r) >> 1
        lo = o << 1
        ro = lo | 1
        if ql <= mid:
            update(lo, l, mid, ql, qr, c)
        if qr > mid:
            update(ro, mid + 1, r, ql, qr, c)
        tree_cnt[o] = tree_cnt[lo] + tree_cnt[ro] - (1 if tree_rc[lo] == tree_lc[ro] else 0)
        tree_lc[o] = tree_lc[lo]
        tree_rc[o] = tree_rc[ro]

    def query(o: int, l: int, r: int, ql: int, qr: int) -> tuple[int, int, int]:
        if ql <= l and r <= qr:
            return tree_cnt[o], tree_lc[o], tree_rc[o]
        push_down(o)
        mid = (l + r) >> 1
        lo = o << 1
        ro = lo | 1
        if qr <= mid:
            return query(lo, l, mid, ql, qr)
        if ql > mid:
            return query(ro, mid + 1, r, ql, qr)
        cnt1, lc1, rc1 = query(lo, l, mid, ql, qr)
        cnt2, lc2, rc2 = query(ro, mid + 1, r, ql, qr)
        same_middle = rc1 == lc2
        return cnt1 + cnt2 - (1 if same_middle else 0), lc1, rc2

    def tree_update(u: int, v: int, c: int) -> None:
        while top[u] != top[v]:
            if depth[top[u]] < depth[top[v]]:
                u, v = v, u
            update(1, 1, n, dfn[top[u]], dfn[u], c)
            u = parent[top[u]]
        if depth[u] > depth[v]:
            u, v = v, u
        update(1, 1, n, dfn[u], dfn[v], c)

    def tree_query(u: int, v: int) -> int:
        ans = 0
        last_u = -1
        last_v = -1
        while top[u] != top[v]:
            if depth[top[u]] >= depth[top[v]]:
                cnt, lc, rc = query(1, 1, n, dfn[top[u]], dfn[u])
                ans += cnt
                if rc == last_u:
                    ans -= 1
                last_u = lc
                u = parent[top[u]]
            else:
                cnt, lc, rc = query(1, 1, n, dfn[top[v]], dfn[v])
                ans += cnt
                if rc == last_v:
                    ans -= 1
                last_v = lc
                v = parent[top[v]]
        if depth[u] >= depth[v]:
            cnt, lc, rc = query(1, 1, n, dfn[v], dfn[u])
            ans += cnt
            if rc == last_u:
                ans -= 1
            if lc == last_v:
                ans -= 1
        else:
            cnt, lc, rc = query(1, 1, n, dfn[u], dfn[v])
            ans += cnt
            if lc == last_u:
                ans -= 1
            if rc == last_v:
                ans -= 1
        return ans

    out: list[str] = []
    for _ in range(m):
        op = next(it)
        if op == b'C':
            u = int(next(it))
            v = int(next(it))
            c = int(next(it))
            tree_update(u, v, c)
        else:
            u = int(next(it))
            v = int(next(it))
            out.append(str(tree_query(u, v)))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:33
 * update_at: 2026-10-05 08:35
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const ll EMPTY_LAZY = -1; // 区间覆盖懒标记的空标记（题目颜色均为非负整数）

ll n, m;
ll init_color[MAXN]; // init_color[i]：节点 i 的初始颜色

// 链式前向星存无向树
int head[MAXN], to[2 * MAXN], nxt_edge[2 * MAXN], edge_cnt;

// 树链剖分数组
int fa[MAXN];          // fa[u]：节点 u 的父亲
int dep[MAXN];         // dep[u]：节点 u 的深度（根深度为 1）
int sz[MAXN];          // sz[u]：以 u 为根的子树大小
int heavy_son[MAXN];   // heavy_son[u]：u 的重儿子，0 表示没有
int top_chain[MAXN];   // top_chain[u]：u 所在重链的链顶
int dfn[MAXN];         // dfn[u]：节点 u 在 dfs 序中的位置
int node_of_dfn[MAXN]; // node_of_dfn[i]：dfs 序第 i 位对应的节点
int dfn_cnt;

// 线段树维护 dfs 序上的连续颜色段
ll seg_cnt[4 * MAXN]; // seg_cnt[o]：区间 o 的颜色段数
ll seg_lc[4 * MAXN];  // seg_lc[o]：区间 o 左端点的颜色
ll seg_rc[4 * MAXN];  // seg_rc[o]：区间 o 右端点的颜色
ll lazy[4 * MAXN];    // lazy[o]：区间整体被覆盖成的颜色，EMPTY_LAZY 表示无标记

// 剖分过程中的辅助数组
int hld_order[MAXN];  // 迭代 dfs 得到、供父节点先于子节点处理的访问顺序
int hld_stack[MAXN];  // 第一遍迭代 dfs 用的栈
int chain_u[MAXN];    // 待处理的节点
int chain_top[MAXN];  // 与 chain_u 对应，待处理节点所在重链的链顶

// 查询结果暂存：区间颜色段数、左端点颜色、右端点颜色
ll res_cnt, res_lc, res_rc;

void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt_edge[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 以 1 为根做轻重链剖分；全程迭代实现，避免链状树递归过深。
void build_hld() {
    int order_cnt = 0;
    int stk_top = 0;

    fa[1] = 0;
    dep[1] = 1;
    hld_stack[++stk_top] = 1;
    while (stk_top > 0) {
        int u = hld_stack[stk_top--];
        hld_order[++order_cnt] = u;
        for (int i = head[u]; i != 0; i = nxt_edge[i]) {
            int v = to[i];
            if (v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            hld_stack[++stk_top] = v;
        }
    }

    // 逆序累加子树大小，同时选出重儿子
    for (int i = 1; i <= n; i++) sz[i] = 1;
    for (int i = order_cnt; i >= 1; i--) {
        int u = hld_order[i];
        int best = 0;
        for (int j = head[u]; j != 0; j = nxt_edge[j]) {
            int v = to[j];
            if (v == fa[u]) continue;
            sz[u] += sz[v];
            if (sz[v] > best) {
                best = sz[v];
                heavy_son[u] = v;
            }
        }
    }

    // 先走重儿子，保证同一条重链上的节点 dfs 序连续
    int chain_ptr = 0;
    chain_u[++chain_ptr] = 1;
    chain_top[chain_ptr] = 1;
    while (chain_ptr > 0) {
        int u = chain_u[chain_ptr];
        int t = chain_top[chain_ptr];
        chain_ptr--;
        dfn_cnt++;
        dfn[u] = dfn_cnt;
        node_of_dfn[dfn_cnt] = u;
        top_chain[u] = t;
        int h = heavy_son[u];
        for (int i = head[u]; i != 0; i = nxt_edge[i]) {
            int v = to[i];
            if (v == fa[u] || v == h) continue;
            chain_u[++chain_ptr] = v;
            chain_top[chain_ptr] = v;
        }
        if (h != 0) {
            chain_u[++chain_ptr] = h;
            chain_top[chain_ptr] = t;
        }
    }
}

// 用左右儿子的信息更新节点 o；交界处颜色相同则两段合并为一段。
void push_up(int o) {
    int lo = o << 1;
    int ro = lo | 1;
    if (seg_rc[lo] == seg_lc[ro]) {
        seg_cnt[o] = seg_cnt[lo] + seg_cnt[ro] - 1;
    } else {
        seg_cnt[o] = seg_cnt[lo] + seg_cnt[ro];
    }
    seg_lc[o] = seg_lc[lo];
    seg_rc[o] = seg_rc[ro];
}

// 把节点 o 的整个区间覆盖成颜色 c
void apply_cover(int o, ll c) {
    lazy[o] = c;
    seg_cnt[o] = 1;
    seg_lc[o] = c;
    seg_rc[o] = c;
}

void push_down(int o) {
    if (lazy[o] == EMPTY_LAZY) return;
    int lo = o << 1;
    int ro = lo | 1;
    apply_cover(lo, lazy[o]);
    apply_cover(ro, lazy[o]);
    lazy[o] = EMPTY_LAZY;
}

void build_seg(int o, ll l, ll r) {
    lazy[o] = EMPTY_LAZY; // 覆盖标记必须在建树时初始化为空，否则 0 会被当成真标记
    if (l == r) {
        ll c = init_color[node_of_dfn[l]];
        seg_cnt[o] = 1;
        seg_lc[o] = c;
        seg_rc[o] = c;
        return;
    }
    ll mid = (l + r) >> 1;
    int lo = o << 1;
    int ro = lo | 1;
    build_seg(lo, l, mid);
    build_seg(ro, mid + 1, r);
    push_up(o);
}

// 把区间 [ql, qr] 覆盖成颜色 c
void update_seg(int o, ll l, ll r, ll ql, ll qr, ll c) {
    if (ql <= l && r <= qr) {
        apply_cover(o, c);
        return;
    }
    push_down(o);
    ll mid = (l + r) >> 1;
    int lo = o << 1;
    int ro = lo | 1;
    if (ql <= mid) update_seg(lo, l, mid, ql, qr, c);
    if (qr > mid) update_seg(ro, mid + 1, r, ql, qr, c);
    push_up(o);
}

// 查询区间 [ql, qr] 的颜色段信息，结果写入 res_cnt / res_lc / res_rc
void query_seg(int o, ll l, ll r, ll ql, ll qr) {
    if (ql <= l && r <= qr) {
        res_cnt = seg_cnt[o];
        res_lc = seg_lc[o];
        res_rc = seg_rc[o];
        return;
    }
    push_down(o);
    ll mid = (l + r) >> 1;
    if (qr <= mid) {
        query_seg(o << 1, l, mid, ql, qr);
        return;
    }
    if (ql > mid) {
        query_seg((o << 1) | 1, mid + 1, r, ql, qr);
        return;
    }
    // 区间跨过中点：查询左右两半后按交界颜色合并
    ll cnt_left, lc_left, rc_left;
    ll cnt_right, lc_right, rc_right;
    query_seg(o << 1, l, mid, ql, qr);
    cnt_left = res_cnt;
    lc_left = res_lc;
    rc_left = res_rc;
    query_seg((o << 1) | 1, mid + 1, r, ql, qr);
    cnt_right = res_cnt;
    lc_right = res_lc;
    rc_right = res_rc;
    if (rc_left == lc_right) {
        res_cnt = cnt_left + cnt_right - 1;
    } else {
        res_cnt = cnt_left + cnt_right;
    }
    res_lc = lc_left;
    res_rc = rc_right;
}

// 把树上 u 到 v 的路径整体覆盖成颜色 c
void tree_update(int u, int v, ll c) {
    while (top_chain[u] != top_chain[v]) {
        if (dep[top_chain[u]] < dep[top_chain[v]]) {
            int tmp = u;
            u = v;
            v = tmp;
        }
        update_seg(1, 1, n, dfn[top_chain[u]], dfn[u], c);
        u = fa[top_chain[u]];
    }
    if (dep[u] > dep[v]) {
        int tmp = u;
        u = v;
        v = tmp;
    }
    update_seg(1, 1, n, dfn[u], dfn[v], c);
}

// 询问树上 u 到 v 的路径颜色段数
ll tree_query(int u, int v) {
    ll ans = 0;
    // last_u / last_v 记录各自方向已跳过的链中最靠下（最靠近当前链）的颜色
    ll last_u = EMPTY_LAZY;
    ll last_v = EMPTY_LAZY;
    while (top_chain[u] != top_chain[v]) {
        if (dep[top_chain[u]] >= dep[top_chain[v]]) {
            query_seg(1, 1, n, dfn[top_chain[u]], dfn[u]);
            ans += res_cnt;
            if (res_rc == last_u) ans--; // 当前链底部与上一段链顶颜色相同，合并
            last_u = res_lc;
            u = fa[top_chain[u]];
        } else {
            query_seg(1, 1, n, dfn[top_chain[v]], dfn[v]);
            ans += res_cnt;
            if (res_rc == last_v) ans--;
            last_v = res_lc;
            v = fa[top_chain[v]];
        }
    }
    // 两点已在同一条重链上，最后查询一段区间并同时与两侧记录的端点颜色去重
    if (dep[u] >= dep[v]) {
        query_seg(1, 1, n, dfn[v], dfn[u]);
        ans += res_cnt;
        if (res_rc == last_u) ans--;
        if (res_lc == last_v) ans--;
    } else {
        query_seg(1, 1, n, dfn[u], dfn[v]);
        ans += res_cnt;
        if (res_lc == last_u) ans--;
        if (res_rc == last_v) ans--;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> init_color[i];
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        add_edge(x, y);
        add_edge(y, x);
    }

    build_hld();
    build_seg(1, 1, n);

    for (int i = 1; i <= m; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'C') {
            ll c;
            cin >> c;
            tree_update(a, b, c);
        } else {
            cout << tree_query(a, b) << '\n';
        }
    }

    return 0;
}

复杂度

时间复杂度：
- 树链剖分预处理需要遍历整棵树，复杂度为 $O(n)$ ；
- 路径修改和查询过程中，两点之间最多经过 $O(\log n)$ 条重链，每条重链在线段树上进行区间操作的时间复杂度为 $O(\log n)$ ，因此单次操作的时间复杂度为 $O(\log^2 n)$ ；
- 处理全部 $m$ 次操作的总时间复杂度为 $O(m \log^2 n)$ 。
空间复杂度：
- 树的邻接表、重链剖分数组（深度、父节点、重儿子、链顶、DFS 序）占用 $O(n)$ 空间；
- 维护颜色段的线段树大小为 $4n$ 节点，空间复杂度为 $O(n)$ ；
- 总空间复杂度为 $O(n)$ 。

总结

本题是树链剖分与线段树结合的典型范式。核心在于将树上路径抽象为若干条连续链的拼接，并在合并线段树节点以及跨越重链时，通过记录端点颜色正确消除边界处相同颜色的重复计数。