「一本通 4.5 练习 4」旅行

GitHub跳转原题关系图返回列表

树链剖分把路径拆成 O(log n) 段 dfn 区间，每种信仰按 dfn 序建静态位置表，二分转成秩区间后用树状数组求和、线段树求最大值。

OJ: roj

题目 ID: 1564

难度:提高+/省选-

标签:树链剖分树状数组线段树路径查询python

创建: 2026-09-30 18:27

更新: 2026-10-07 13:50

前置题目

luogu P2590[ZJOI2008] 树的统计B 的 path_spans 在代码里直接复用 A 教的「树链剖分把路径拆成连续 dfn 区间」这一步（同款选链顶较深一侧摘段再跳父亲），再叠加 A 未教的按信仰切分状态、成员 dfn 位置表二分转秩区间，以及树状数组求和/线段树求最大值，属于在树剖模板上叠加多流程的综合题。roj 1562软件包管理器B 的 path_spans 直接复用 A 教的重链头部跳跃拆路径：每次摘下一段连续的 [pos(head), pos(x)] 区间、再跳到链顶父亲，A 用它逐段置 1，B 用它逐段二分求秩后统计，B 只是把单条根到 x 路径推广为 x→y 并叠加按信仰分堆。

形式化题目

给定一棵 $n$ 个点的树，点 $i$ 有两个属性：评级 $w_i$ （正整数）与信仰 $c_i$ （ $1 \sim C$ 的正整数）。按顺序处理 $q$ 个操作，并对每个查询输出答案：

$CC\ x\ c$ ：把 $c_x$ 改为 $c$ ；
$CW\ x\ w$ ：把 $w_x$ 改为 $w$ ；
$QS\ x\ y$ ：记路径 $x \rightsquigarrow y$ （唯一最短路，含两端）上满足 $c_u = c_x$ 的点集为 $S$ ，输出 $\sum_{u \in S} w_u$ ；
$QM\ x\ y$ ：同上，输出 $\max_{u \in S} w_u$ 。

保证每次查询时 $c_x = c_y$ ，且单次旅行期间所有属性不变。

样例输入：

text

样例输出：

text

下图为样例初始状态，每个节点标注 dfn 编号、信仰与评级（dfn 是后文树链剖分的编号，此处先给结果）：

graph TD
    c1["城市 1<br/>dfn 0 · 信仰 1 · 评级 3"]
    c2["城市 2<br/>dfn 4 · 信仰 3 · 评级 2"]
    c3["城市 3<br/>dfn 1 · 信仰 2 · 评级 1"]
    c4["城市 4<br/>dfn 2 · 信仰 3 · 评级 3"]
    c5["城市 5<br/>dfn 3 · 信仰 1 · 评级 5"]
    c1 --> c2
    c1 --> c3
    c3 --> c4
    c3 --> c5

样例逐条对答案：QS 1 5 的路径是 $1 \to 3 \to 5$ ，信仰 1 的城市只有 1 和 5，和为 $3 + 5 = 8$ ；CC 3 1 后城市 3 也命中，和变 $3 + 1 + 5 = 9$ ； CW 3 3 把城市 3 的评级改成 3，和为 $3 + 3 + 5 = 11$ ； QM 2 4 的路径是 $2 \to 1 \to 3 \to 4$ ，其中信仰 3 的城市是 2 和 4，最大值为 $\max(2, 3) = 3$ 。

正解

思路

1. 朴素做法与两个瓶颈

每次查询先求 LCA，再沿路径逐点走：信仰与 $c_x$ 相同就累加 / 比较。单次 $O(n)$ ， $q$ 次最坏 $O(nq) = 10^{10}$ ，显然超时。逐点扫暴露两个瓶颈：

瓶颈一：路径本身太长。 一条链可能有 $n$ 个点，逐点走无法避免；
瓶颈二：段内混着各种信仰。 即便把路径切短，每段里仍只有少数点属于 $c_x$ ，普通线段树统计的是区间内所有点，回答不了「只算一种信仰」。

两个瓶颈分别用两步优化消除。

2. 瓶颈一：树链剖分把路径拆成 O(log n) 段 dfn

重儿子定义为子树最大的儿子，其余为轻儿子；重链是重儿子首尾相接的链。按「先访问重儿子」的顺序给每个点编一个 dfn（走完一条重链才折返去轻儿子），则每条重链得到一段连续的 dfn 区间。路径 $x \rightsquigarrow y$ 的拆法：只要 $\mathrm{head}[x] \neq \mathrm{head}[y]$ ，就把链顶较深的一侧整段 $[\mathrm{dfn}(\mathrm{head}[x]), \mathrm{dfn}(x)]$ 摘下来（此时 $x$ 一侧从链顶到 $x$ 整段都在路径上），再把 $x$ 跳到链顶的父亲；两侧同链时，浅者就是 LCA，收尾一段 $[\mathrm{dfn}(\mathrm{LCA}), \mathrm{dfn}(\text{深者})]$ 。每次摘段至少爬一条轻边，而从根到任何点的轻边不超过 $\log_2 n$ 条（每爬一条轻边子树大小至少翻倍），所以路径被拆成 $O(\log n)$ 段连续 dfn 闭区间（代码里的 path_spans，全程迭代，链形树也不会爆递归）。

3. 瓶颈二：按信仰把状态切开

关键观察：一次查询只问 $c_x$ 这一种信仰——其他信仰无论怎么变都与本次无关。于是可以把点权状态按信仰切开：每种信仰各维护一份独立结构，查询时只碰 $c_x$ 那一份，彼此零耦合。按信仰分堆的难点是「信仰成员随时因 CC 变动」，两个观察化解它：

成员全集静态可预算：城市只有初始信仰和 CC 指定的新信仰两种可能，预扫一遍全部 CC 事件就得到每种信仰「出现过」的成员集合，总量不超过 $n + q$ ；
成员的 dfn 固定：树不会变，把每种信仰的成员按 dfn 升序存成位置表 pos，这张表一旦建好永不改变，随时间变化的只有「该城市此刻记多少值」。

有了 dfn 升序的位置表，查询段 $[l, r]$ 内信仰 $c$ 的城市就是 pos 中的 $[\mathrm{bisect\_left}(l),\ \mathrm{bisect\_right}(r))$ 一段连续秩区间—— 两次二分就把 dfn 区间翻译成了秩区间。每种信仰剩下的需求只有「单点改值 + 秩区间求和 + 秩区间最大值」，正好是树状数组与完全二叉树线段树的活， $k_c$ 个成员的结构只占 $O(k_c)$ 空间，不需要 C++ 正解里为省空间常用的动态开点线段树。

取值约定：城市 $x$ 在信仰 $c$ 结构里的值 = $w_x$ （若 $c_x = c$ ）否则 $0$ 。三类维护动作由此落地：

CW x w：改 weight 后，把自己信仰那一份的单点值刷成 $w$ ；
CC x c：旧信仰置 $0$ 、新信仰置 $w_x$ ，两次单点改值；
初始：每座城市写进初始信仰那一份。

0 是安全的中性元：评级恒为正，记 0 的城市不会贡献求和，也抢不走最大值；且查询端点自身必然命中、评级 $> 0$ ，所以空段的 0 永远不影响答案。

4. 样例推演

以初始状态的 QS 1 5 为例：路径拆成第 1 段 $[3, 3]$ （城市 5）与第 2 段 $[0, 1]$ （城市 1、3）；信仰 1 的位置表是 $[0, 3]$ ，逐段二分出秩区间再查值。下表每列是一段拆分，四行依次是该段的 dfn 区间、段内信仰相同的城市、翻译出的秩范围与它的评级贡献：

项目	第 1 段	第 2 段
dfn 区间	$[3, 3]$	$[0, 1]$
命中城市（信仰相同）	5	1
位置表秩范围	$[1, 2)$	$[0, 1)$
评级贡献	5	3

各段贡献相加即路径总和： $5 + 3 = 8$ ，与样例第一行一致。 CC 3 1 后城市 3 的 dfn 1 插入位置表变成 $[0, 1, 3]$ ，同一路径命中 $5 + (3 + 1) = 9$ 。

5. 正确性要点

拆段不重不漏：每段都是路径上的一段连续弧，段间首尾相接，覆盖整条路径；
秩区间与 dfn 区间等价：位置表 dfn 升序，bisect 的左右边界恰好圈出段内成员；
单点维护归纳正确：初始、CW、CC 三种写入都遵守取值约定，因而任意时刻结构里的值都等于约定值，前缀和与区间最大值自然正确；
与常见 C++ 正解（树剖 + 每信仰动态开点线段树）复杂度同阶，本解用「预扫事件预算成员」换掉动态开点，常数与实现都更小。

上面三步分别对应 main.py 的 path_spans（拆段）、paint（单点改值）与 query_sum / query_max（段内二分 + 统计）。

代码

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#!/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:34
# update_at: 2026-09-30 18:34

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict
from collections.abc import Iterator

# 每个信仰一份结构：(dfn 升序位置表, 求和树状数组, 最大值线段树)。
# 信仰成员按 dfn 排序后是静态的，秩可随时二分得到，因此不必动态开点。
Tree = tuple[list[int], list[int], list[int]]
HLD = tuple[list[int], list[int], list[int], list[int]]  # (链顶, 深度, 父亲, dfn)


def build_hld(n: int, adj: list[list[int]], root: int = 1) -> HLD:
    """树链剖分：先算子树大小与重儿子，再按重链优先顺序给 dfn 编号。"""
    parent = [0] * (n + 1)
    dep = [0] * (n + 1)
    order: list[int] = []
    stack = [root]
    while stack:                                    # 迭代 DFS，避免链形树爆递归
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                dep[v] = dep[u] + 1
                stack.append(v)

    size = [1] * (n + 1)
    heavy = [0] * (n + 1)                           # 重儿子：子树最大的儿子
    for u in reversed(order):                       # 逆 DFS 序保证儿子先算完
        top, big = 0, 0
        for v in adj[u]:
            if v != parent[u]:
                size[u] += size[v]
                if size[v] > top:
                    top, big = size[v], v
        heavy[u] = big

    dfn = [0] * (n + 1)
    head = [0] * (n + 1)
    head[root] = root
    todo = [root]
    clock = 0
    while todo:                                     # 每条链拿到连续的一段 dfn
        u = todo.pop()
        h = head[u]
        w = u
        while w:                                    # 沿重链一路走到叶子
            dfn[w] = clock
            clock += 1
            head[w] = h
            for v in adj[w]:                        # 轻儿子各自成链，稍后处理
                if v != parent[w] and v != heavy[w]:
                    head[v] = v
                    todo.append(v)
            w = heavy[w]
    return head, dep, parent, dfn


def path_spans(x: int, y: int, hld: HLD) -> Iterator[tuple[int, int]]:
    """把树上 x→y 的路径拆成若干段连续 dfn 闭区间（树链剖分标准拆法）。"""
    head, dep, parent, dfn = hld
    while head[x] != head[y]:                       # 不在同一条链上时，先走链顶更深的一侧
        if dep[head[x]] < dep[head[y]]:
            x, y = y, x
        yield dfn[head[x]], dfn[x]
        x = parent[head[x]]
    if dep[x] > dep[y]:                             # 同链时浅的是 LCA
        x, y = y, x
    yield dfn[x], dfn[y]


def fenwick_add(bit: list[int], i: int, delta: int) -> None:
    """树状数组单点加：第 i 个位置（1 起）增加 delta。"""
    while i < len(bit):
        bit[i] += delta
        i += i & -i


def fenwick_sum(bit: list[int], i: int) -> int:
    """树状数组前缀和：前 i 个元素（1 起）之和。"""
    total = 0
    while i:
        total += bit[i]
        i -= i & -i
    return total


def seg_max(seg: list[int], size: int, l: int, r: int) -> int:
    """线段树区间最大值：半开区间 [l, r) 叶子的最大值，空区间记 0。"""
    res = 0
    l += size
    r += size
    while l < r:
        if l & 1:
            res = max(res, seg[l])
            l += 1
        if r & 1:
            r -= 1
            res = max(res, seg[r])
        l >>= 1
        r >>= 1
    return res


def paint(tree: Tree, x: int, v: int, dfn: list[int]) -> None:
    """把城市 x 在某信仰结构里的取值改成 v（0 表示当前不信仰它）。"""
    pos, bit, seg = tree
    i = bisect_left(pos, dfn[x])                    # dfn 在位置表里必然存在，二分即得秩
    size = len(seg) >> 1
    j = i + size
    delta = v - seg[j]                              # 树状数组只记增量，旧值就存在叶子里
    if delta:
        seg[j] = v
        while j > 1:                                # 叶子回溯更新整条链上的最大值
            j >>= 1
            seg[j] = max(seg[j << 1], seg[j << 1 | 1])
        fenwick_add(bit, i + 1, delta)


def query_sum(x: int, y: int, c: int, trees: dict[int, Tree], hld: HLD) -> int:
    """查询 x→y 路径上信仰 c 的城市评级总和。"""
    pos, bit, _ = trees[c]
    return sum(
        fenwick_sum(bit, bisect_right(pos, r)) - fenwick_sum(bit, bisect_left(pos, l))
        for l, r in path_spans(x, y, hld)           # 每段区间二分出秩范围再求和
    )


def query_max(x: int, y: int, c: int, trees: dict[int, Tree], hld: HLD) -> int:
    """查询 x→y 路径上信仰 c 的城市评级最大值。"""
    pos, _, seg = trees[c]
    size = len(seg) >> 1
    return max(
        seg_max(seg, size, bisect_left(pos, l), bisect_right(pos, r))
        for l, r in path_spans(x, y, hld)           # 评级恒为正，空段记 0 不影响答案
    )


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    it = iter(tokens)
    n = int(next(it))
    q = int(next(it))
    weight = [0] * (n + 1)                          # 当前评级
    rel = [0] * (n + 1)                             # 当前信仰
    for i in range(1, n + 1):
        weight[i] = int(next(it))
        rel[i] = int(next(it))

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

    # 第一遍扫 CC：记下每座城市出现过的信仰，成员静态，按 dfn 升序建位置表。
    ever: dict[int, list[int]] = defaultdict(list)
    for i in range(1, n + 1):
        ever[rel[i]].append(i)

    ops: list[tuple[bytes, int, int]] = []
    for _ in range(q):
        op = next(it)
        x = int(next(it))
        y = int(next(it))
        ops.append((op, x, y))
        if op == b"CC":
            ever[y].append(x)

    hld = build_hld(n, adj)
    dfn = hld[3]

    trees: dict[int, Tree] = {}
    for c, members in ever.items():
        members.sort(key=dfn.__getitem__)
        size = 1 << (len(members) - 1).bit_length()  # 完全二叉树叶子数取 2 的幂
        trees[c] = ([dfn[x] for x in members], [0] * (len(members) + 1), [0] * (2 * size))
    for i in range(1, n + 1):                        # 初始全员在自己的信仰里
        paint(trees[rel[i]], i, weight[i], dfn)

    out: list[str] = []
    for op, x, y in ops:
        if op == b"QS":
            out.append(str(query_sum(x, y, rel[x], trees, hld)))
        elif op == b"QM":
            out.append(str(query_max(x, y, rel[x], trees, hld)))
        elif op == b"CW":
            weight[x] = y
            paint(trees[rel[x]], x, y, dfn)
        else:                                        # CC x c：先退出旧信仰，再加入新信仰
            if rel[x] != y:
                paint(trees[rel[x]], x, 0, dfn)
                rel[x] = y
                paint(trees[y], x, weight[x], dfn)

    print("\n".join(out))


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
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338/**
 * 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:36
 * update_at: 2026-10-05 08:46
 */
// 树链剖分把路径拆成 O(log n) 段 dfn 区间；每种信仰单独一份结构：
// 成员集合静态可预算（初始信仰 + 所有 CC 指定的新信仰），成员的 dfn 固定，
// 按 dfn 升序建成静态位置表；dfn 区间两次二分翻译成连续秩区间，
// 秩区间求和用树状数组、求最大值用完全二叉树线段树，单点改值 O(log n)。
// 取值约定：城市 x 在信仰 c 结构里的值 = w_x（若 belief[x] == c）否则 0，
// 评级恒为正，0 是安全的中性元（不贡献和，也抢不走最大值）。

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;

const int MAXN = 100005;      // n, q <= 1e5：城市数与操作数上限
const int MAXM = 2 * MAXN;    // 成员总数不超过 n + q

int n, q;

// 树结构（链式前向星）
int head_[MAXN], nxt[MAXN << 1], to[MAXN << 1], cnt_edge = 0;
// 树剖用：父亲、深度、子树大小、重儿子、重链顶、dfn 编号（dfn 从 0 开始）
int fa[MAXN], dep[MAXN], sz[MAXN], heavy_[MAXN], top_[MAXN], dfn[MAXN];
int order_[MAXN], order_cnt = 0; // 第一遍 DFS 的访问序
int dfn_node[MAXN];              // dfn -> 城市编号，建位置表时反查

ll weight[MAXN];   // 每座城市当前评级
int belief[MAXN];  // 每座城市当前信仰
ll cur_val[MAXN];  // 城市 x 当前在自己信仰结构里的取值（其余结构里视为 0）

struct Query {     // 一条操作：两个字符 + 两个参数
    char op[3];
    ll x, y;
} qs[MAXN];

// ---- 按信仰分堆的静态结构 ----
int pos_sorted[MAXM];         // 所有信仰的位置表依次存放：按 dfn 升序的城市编号
int table_start[MAXM];        // 信仰 c 的位置表在 pos_sorted 里的起始下标
int table_len[MAXM];          // 信仰 c 的位置表长度
// 注意：一个城市可能同时出现在多张表里（初始信仰表 + CC 目标信仰表），
// 所以「x 在信仰 c 表中的秩」不能存成单值，要按 dfn 在表内二分得到。
ll keys[MAXM];                // 预算成员用的键：c * (n+1) + dfn[x]，排序去重

ll bit[MAXM];                // 树状数组：各信仰的表分段共用一个前缀空间（ll 防前缀和溢出）
ll seg_tree[MAXM * 4];        // 完全二叉树线段树，各信仰的树依次存放
int seg_base[MAXM];           // 信仰 c 的线段树堆区在 seg_tree 里的起始下标
int seg_size[MAXM];           // 信仰 c 的线段树叶子数（2 的幂）
ll ans_out[MAXN];             // 每条查询的输出，最后统一打印

// 加边
void add_edge(int a, int b) {
    cnt_edge++;
    nxt[cnt_edge] = head_[a];
    to[cnt_edge] = b;
    head_[a] = cnt_edge;
}

// 第一遍 DFS（迭代，防链形树爆栈）：求父亲、深度、访问序，再逆序算子树大小与重儿子
void dfs_size() {
    static int stk[MAXN];
    int tp = 0;
    stk[++tp] = 1;
    fa[1] = 0;
    dep[1] = 0;
    while (tp) {
        int u = stk[tp--];
        order_[++order_cnt] = u;
        for (int e = head_[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v != fa[u]) {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                stk[++tp] = v;
            }
        }
    }
    for (int i = order_cnt; i >= 1; i--) { // 逆访问序：儿子先于父亲被处理
        int u = order_[i];
        sz[u] = 1;
        int big = 0; // 子树最大的儿子
        for (int e = head_[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v != fa[u]) {
                sz[u] += sz[v];
                if (big == 0 || sz[v] > sz[big]) big = v;
            }
        }
        heavy_[u] = big;
    }
}

// 第二遍（迭代）：沿重链优先给 dfn 编号，每条重链拿到一段连续 dfn
void dfs_dfn() {
    static int stk[MAXN];
    int tp = 0;
    stk[++tp] = 1;
    top_[1] = 1;
    int clock_ = 0;
    while (tp) {
        int u = stk[tp--];
        int h = top_[u];
        for (int w = u; w; w = heavy_[w]) { // 沿重链一路走到叶子
            dfn[w] = clock_;
            dfn_node[clock_] = w;
            clock_++;
            top_[w] = h;
            // 轻儿子各自成链，压栈稍后处理
            for (int e = head_[w]; e; e = nxt[e]) {
                int v = to[e];
                if (v != fa[w] && v != heavy_[w]) {
                    top_[v] = v;
                    stk[++tp] = v;
                }
            }
        }
    }
}

// 把路径 x -> y 拆成若干段连续 dfn 闭区间，存进 span_l / span_r
int span_l[70], span_r[70]; // 单条路径最多约 2*log2(n) 段，70 足够
int span_cnt = 0;
void path_spans(int x, int y) {
    span_cnt = 0;
    while (top_[x] != top_[y]) { // 不在同一条链上，摘链顶更深的一侧整段
        if (dep[top_[x]] < dep[top_[y]]) {
            int t = x; x = y; y = t;
        }
        span_cnt++;
        span_l[span_cnt] = dfn[top_[x]];
        span_r[span_cnt] = dfn[x];
        x = fa[top_[x]];
    }
    if (dep[x] > dep[y]) { // 同链时浅的是 LCA，收尾一段
        int t = x; x = y; y = t;
    }
    span_cnt++;
    span_l[span_cnt] = dfn[x];
    span_r[span_cnt] = dfn[y];
}

// ---- 树状数组（1 起）：单点加 / 前缀和，全长 MAXM，各信仰的表分段共用 ----
void fenwick_add(int i, int delta) {
    for (; i < MAXM; i += i & (-i)) bit[i] += delta;
}
ll fenwick_sum(int i) {
    ll s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}

// 把信仰 c 的线段树第 i 个叶子（0 起）改成 v，并回溯更新祖先的最大值
void seg_update(int c, int i, ll v) {
    int base = seg_base[c], size = seg_size[c];
    int j = size + i; // 转成堆下标
    seg_tree[base + j] = v;
    for (j >>= 1; j >= 1; j >>= 1) {
        seg_tree[base + j] = std::max(seg_tree[base + (j << 1)], seg_tree[base + (j << 1 | 1)]);
    }
}

// 信仰 c 的线段树区间最大值：叶子区间 [l, r) 内的最大值，空区间记 0
ll seg_max(int c, int l, int r) {
    int base = seg_base[c], size = seg_size[c];
    ll res = 0;
    l += size;
    r += size;
    while (l < r) {
        if (l & 1) { res = std::max(res, seg_tree[base + l]); l++; }
        if (r & 1) { r--; res = std::max(res, seg_tree[base + r]); }
        l >>= 1;
        r >>= 1;
    }
    return res;
}

// 在信仰 c 的位置表里二分：返回第一个 dfn >= v 的秩（0 起）
int bisect_first(int c, int v) {
    int lo = table_start[c], hi = table_start[c] + table_len[c]; // [lo, hi)
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (dfn[pos_sorted[mid]] < v) lo = mid + 1; else hi = mid;
    }
    return lo - table_start[c];
}

// 在信仰 c 的位置表里二分：返回第一个 dfn > v 的秩（0 起）
int bisect_last(int c, int v) {
    int lo = table_start[c], hi = table_start[c] + table_len[c];
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (dfn[pos_sorted[mid]] <= v) lo = mid + 1; else hi = mid;
    }
    return lo - table_start[c];
}

// 把城市 x 在信仰 c 结构里的取值改成 v（v=0 表示 x 当前不信仰 c）。
// x 的 dfn 必在 c 的表里（成员全集已预算），秩由表内二分得到。
// 树状数组只吃增量：旧值可由 cur_val 推出（x 只在 belief[x] 的表里非 0）。
void paint(int c, int x, ll v) {
    ll oldv = 0;
    if (belief[x] == c) oldv = cur_val[x];
    if (oldv == v) return;
    if (belief[x] == c) cur_val[x] = v;
    int i = bisect_first(c, dfn[x]);
    seg_update(c, i, v);
    fenwick_add(table_start[c] + i + 1, v - oldv);
}

// 查询 x->y 路径上信仰 c 的评级和 / 最大值
ll query_sum(int x, int y, int c) {
    path_spans(x, y);
    ll res = 0;
    for (int k = 1; k <= span_cnt; k++) {
        int i1 = bisect_first(c, span_l[k]);
        int i2 = bisect_last(c, span_r[k]);
        if (i2 > i1) {
            res += fenwick_sum(table_start[c] + i2) - fenwick_sum(table_start[c] + i1);
        }
    }
    return res;
}
ll query_max(int x, int y, int c) {
    path_spans(x, y);
    ll res = 0; // 评级恒为正且端点必命中，0 不会被返回
    for (int k = 1; k <= span_cnt; k++) {
        int i1 = bisect_first(c, span_l[k]);
        int i2 = bisect_last(c, span_r[k]);
        if (i2 > i1) {
            res = std::max(res, seg_max(c, i1, i2));
        }
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld %d", &weight[i], &belief[i]);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add_edge(a, b);
        add_edge(b, a);
    }
    for (int i = 1; i <= q; i++) scanf("%s %lld %lld", qs[i].op, &qs[i].x, &qs[i].y);

    dfs_size();
    dfs_dfn();

    // 预算成员全集：初始 n 个 + 所有 CC 事件的目标成员，键排序去重后按信仰分组。
    // 键 = c * (n+1) + dfn[x]：同键去重即同 (信仰, 城市) 去重，组内天然按 dfn 升序。
    int cnt_keys = 0;
    for (int i = 1; i <= n; i++) {
        keys[cnt_keys++] = (ll)belief[i] * (n + 1) + dfn[i];
    }
    for (int i = 1; i <= q; i++) {
        if (qs[i].op[0] == 'C' && qs[i].op[1] == 'C') {
            keys[cnt_keys++] = (ll)qs[i].y * (n + 1) + dfn[qs[i].x];
        }
    }
    std::sort(keys, keys + cnt_keys);
    cnt_keys = (int)(std::unique(keys, keys + cnt_keys) - keys);

    // 分组建表：每种信仰一段位置表 + 一棵 2 的幂叶子的线段树
    int mem_cnt = 0;   // 已放入 pos_sorted 的成员数
    int seg_top = 1;   // seg_tree 已用到的堆下标（从 1 开始，各树顺次存放）
    for (int k = 0; k < cnt_keys; k++) {
        int c = (int)(keys[k] / (n + 1));
        int d = (int)(keys[k] % (n + 1));
        if (k == 0 || c != (int)(keys[k - 1] / (n + 1))) {
            // 新信仰：先收尾上一棵树（无），再为本信仰开表开树
            table_start[c] = mem_cnt;
            table_len[c] = 0;
            int size = 1;
            while (size < 1) size <<= 1; // 占位，下面按整组长度再定
            // 叶子数先按组内剩余数量上界暂定，整组结束时用实际长度重定不划算，
            // 因此先扫出该信仰的成员个数
            int j = k;
            while (j < cnt_keys && (int)(keys[j] / (n + 1)) == c) j++;
            int len = j - k;
            int size2 = 1;
            while (size2 < len) size2 <<= 1;
            seg_base[c] = seg_top; // 堆区占 2*size2 个下标（含 0 号不用）
            seg_size[c] = size2;
            for (int t = 0; t < 2 * size2; t++) seg_tree[seg_top + t] = 0;
            seg_top += 2 * size2;
        }
        int x = dfn_node[d];
        pos_sorted[mem_cnt] = x;
        mem_cnt++;          // 秩 = mem_cnt - table_start[c] - 1，用时按 dfn 表内二分
        table_len[c]++;
    }
    for (int i = 1; i <= n; i++) { // 初始全员在自己的信仰里
        cur_val[i] = weight[i];
        int c = belief[i];
        int r = bisect_first(c, dfn[i]);
        int base = seg_base[c], size = seg_size[c];
        seg_tree[base + size + r] = weight[i];
        fenwick_add(table_start[c] + r + 1, weight[i]);
    }
    // 初始写值后自底向上建各信仰线段树：直接对每个内部节点取两儿子最大值
    for (int k = 0; k < cnt_keys; k++) {
        int c = (int)(keys[k] / (n + 1));
        if (k > 0 && c == (int)(keys[k - 1] / (n + 1))) continue;
        int base = seg_base[c], size = seg_size[c];
        for (int j = size - 1; j >= 1; j--) {
            seg_tree[base + j] = std::max(seg_tree[base + (j << 1)], seg_tree[base + (j << 1 | 1)]);
        }
    }

    // 逐条处理操作
    int out_cnt = 0;
    for (int i = 1; i <= q; i++) {
        int x = (int)qs[i].x;
        if (qs[i].op[0] == 'Q') {
            int c = belief[x]; // 查询只问 c_x 这一种信仰
            if (qs[i].op[1] == 'S') ans_out[++out_cnt] = query_sum(x, (int)qs[i].y, c);
            else ans_out[++out_cnt] = query_max(x, (int)qs[i].y, c);
        } else if (qs[i].op[1] == 'W') { // CW x w：改评级，刷自己信仰那一份
            weight[x] = qs[i].y;
            paint(belief[x], x, weight[x]);
        } else { // CC x c：旧信仰置 0，新信仰置 w_x
            int c = (int)qs[i].y;
            if (belief[x] != c) {
                paint(belief[x], x, 0);
                belief[x] = c;
                paint(c, x, weight[x]);
            }
        }
    }
    for (int i = 1; i <= out_cnt; i++) printf("%lld\n", ans_out[i]);
    return 0;
}

复杂度

预处理：两次迭代 DFS 树剖 $O(n)$ ，扫事件 $O(q)$ ，各信仰成员排序 $\sum_c k_c \log k_c \leqslant (n + q)\log n$ ，初始 $n$ 次写入 $O(n \log n)$ ；
单点修改（CC / CW）：二分定秩 + 树状数组更新 + 线段树回溯， $O(\log n)$ ；
单次查询（QS / QM）： $O(\log n)$ 段，每段两次二分加一次区间查询 $O(\log n)$ ，共 $O(\log^2 n)$ ；
总时间 $O((n + q)\log^2 n)$ ，与正解同阶；空间 $O(n + q)$ ：位置表、树状数组与线段树持有的整数总数均为 $O(n + q)$ 量级。
实测 data 仓 20 组真实数据（ $n, q \leqslant 10^5$ ）输出全部一致，单组 $0.5 \sim 1.0$ s、峰值内存约 100 MB；OJ 端 1 s 限时对 Python 偏紧，代码用一次 read().split() 读入与全迭代实现压常数。

总结

本题是「带信仰限制的动态树路径查询」：信仰是点的颜色，查询只问端点那一种颜色。朴素逐点扫的两个瓶颈——路径太长、区间混色——分别由树链剖分和按信仰分堆解决：树剖把路径压成 $O(\log n)$ 段连续 dfn 区间；「一次只问一种信仰」让状态可以按信仰完全切开，再靠「预扫事件知成员全集、成员 dfn 固定」把动态改色降级成单点置值， dfn 区间两次二分即得连续秩区间，段内求和与求最值交给树状数组和线段树。两步合起来得到 $O((n + q)\log^2 n)$ 的在线解法。凡是「带颜色限制的路径 / 子树查询」，都可以考虑这种「按颜色分堆 + 成员预算」的拆法。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6带信仰限制的路径查询
 |- 瓶颈一：逐点爬路径 O(n) -> 树链剖分把路径拆成 O(log n) 段 dfn 区间
 |- 瓶颈二：区间混着各种信仰 -> 按信仰切开状态，每信仰一份独立结构
 |   `- 成员 dfn 静态：dfn 区间 --两次二分--> 连续秩区间
 `- 秩区间求和 / 求最值 + 单点改值 -> 树状数组 + 线段树
    `- 逐段累加（0 作中性元）= 路径答案

先看每条分支解决的是哪个瓶颈：上半两支把「路径太长」「只统计一种信仰」分别拆掉，中间一支用「成员 dfn 静态」把动态改色降级成单点置值，最后一支给出段内统计的落地结构。顺着箭头走一遍样例 QS 1 5，就能看到拆段、二分、累加如何合成最终答案。

【题目描述】

S 国有 $N$ 个城市，编号从 $1$ 到 $N$ 。城市间用 $N-1$ 条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教，S 国境内总共有 $C$ 种不同的宗教。

S 国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S 国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在 S 国的历史上常会发生以下几种事件：

1、 $CC\ x\ c$ ：城市 $x$ 的居民全体改信了 $c$ 教；

2、 $CW\ x\ w$ ：城市 $x$ 的评级调整为 $w$ ；

3、 $QS\ x\ y$ ：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级总和；

4、 $QM\ x\ y$ ：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。

为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

【输入】

输入的第一行包含整数 $N$ ， $Q$ 依次表示城市数和事件数。

接下来 $N$ 行，第 $i+1$ 行两个整数 $W_i$ ， $C_i$ 依次表示记录开始之前，城市 $i$ 的评级和信仰。

接下来 $N-1$ 行每行两个整数 $x$ ， $y$ 表示一条双向道路。

接下来 $Q$ 行，每行一个操作，格式如上所述。

【输出】

对每个 $QS$ 和 $QM$ 事件，输出一行，表示旅行者记下的数字。

【输入样例】

text

【输出样例】

text

【提示】

数据范围与提示：

对所有的数据， $Q\leq10^5 , C\leq10^5$ ，对所有 $QS$ 和 $QM$ 事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于 $10^4$ 的正整数，且宗教值不大于 $C$ 。

【来源】

一本通在线评测