树链剖分把路径变区间，宗教过滤给出三种实现：按宗教动态开点线段树（主解）、离线离散化的普通线段树、单树每节点挂 map，附实测对比。
OJ: luogu
题目 ID: P3313
难度:提高+/省选-
目录
形式化题目
给定一棵
CC x c：把点的颜色改成 ，即 ； CW x w：把点的权值改成 ，即 ； QS x y：在路径上，把所有颜色等于 的点的权值相加并输出，即求 ； QM x y：在路径上，取所有颜色等于 的点的权值最大值并输出，即求 。
数据保证每次查询满足
解法总览
三个解法共享前一半：树链剖分把路径变成
树链剖分部分：两次 DFS 求每个点的重儿子与链头，再按「先重儿子」的顺序重新编号（dfn）。样例的树很小，剖分结果可以直接摊开看：点
图的左半边是树：蓝色粗线是重儿子边，它们连成重链
QS 5 1 这条路径（
三条分支的差别只在下一层：
| 解法 | 过滤宗教的手段 | 时间（预处理 / 单点 / 查询） | 空间 | 实测（ |
对应代码 |
|---|---|---|---|---|---|
| 一（推荐提交） | 每种宗教一棵线段树，共享节点池、动态开点 | 169–293 ms，33–61 MiB | main.cpp |
||
| 二 | 每种宗教一棵普通线段树，坐标先离线离散化成「该宗教历史上出现过的 dfn」 | 162–276 ms，20–28 MiB | main2.cpp |
||
| 三 | 只开一棵 dfn 线段树，每个节点挂一张「宗教 → 摘要」的 map |
1.8–6.3 s（换哈希表 1.2–3.6 s），95–119 MiB | main3.cpp |
三者的关系：解法一和解法二是同一个「按宗教拆树」模型，差别只在坐标空间怎么来（在线开点 vs 离线压缩）；解法三完全不拆树，把宗教当成线段树节点里的一维映射，写法最短、最慢。解法一不需要离线、常数和空间都适中，所以作为推荐提交的主解。
暴力解法
适用范围
brute.cpp 里 MAXN = 105 的上界。它的用途有两个：把题意写成可执行的说明书，以及作为三个解法的对拍基准。
思路
先用一次 BFS 把树定根（根取 parent 与深度 depth。查询时只做一件事：把两个端点沿父亲往上爬，逐点判断宗教。
具体是三步：先让较深的一端单独往上爬，直到两端深度相同；然后两端一起往上爬，直到相遇；路径上的每个点（包括起点和终点）都检查一次宗教是否等于 CC 与 CW 直接改数组，
代码
cpp
/**
* 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-08-12 22:59
* update_at: 2026-08-12 23:00
*/
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 查询时沿路径逐点向上爬，只统计与起点同宗教的城市评级。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, q;
int w[MAXN]; // w[i] 城市 i 的评级
int col[MAXN]; // col[i] 城市 i 的宗教
vector<int> g[MAXN]; // 树的邻接表
int parent[MAXN]; // 以 1 为根的父亲
int depth[MAXN]; // 深度
// 从根 1 出发 BFS，得到每个节点的父亲与深度，供路径逐点爬使用。
void build_root(int root) {
queue<int> que;
que.push(root);
parent[root] = 0;
depth[root] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int v : g[u]) {
if (v == parent[u]) continue;
parent[v] = u;
depth[v] = depth[u] + 1;
que.push(v);
}
}
}
// 朴素路径查询：让较深的端点不断向上爬，逐点判断宗教是否相同。
// 爬的过程中把符合条件的评级累加进和、更新最大值。
void path_query(int x, int y, int rel, int &tsum, int &tmax) {
while (depth[x] > depth[y]) {
if (col[x] == rel) {
tsum += w[x];
tmax = max(tmax, w[x]);
}
x = parent[x];
}
while (depth[y] > depth[x]) {
if (col[y] == rel) {
tsum += w[y];
tmax = max(tmax, w[y]);
}
y = parent[y];
}
// 现在 x、y 同深度，一起向上爬直到相遇。
while (x != y) {
if (col[x] == rel) {
tsum += w[x];
tmax = max(tmax, w[x]);
}
if (col[y] == rel) {
tsum += w[y];
tmax = max(tmax, w[y]);
}
x = parent[x];
y = parent[y];
}
// x == y，是路径的公共祖先，只统计一次。
if (col[x] == rel) {
tsum += w[x];
tmax = max(tmax, w[x]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> col[i];
}
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
build_root(1);
while (q--) {
string op;
int x, y;
cin >> op >> x >> y;
if (op == "CC") {
col[x] = y;
} else if (op == "CW") {
w[x] = y;
} else {
int tsum = 0, tmax = 0;
path_query(x, y, col[x], tsum, tmax);
if (op == "QS") {
cout << tsum << '\n';
} else {
cout << tmax << '\n';
}
}
}
return 0;
}复杂度与瓶颈
- 时间：预处理
；单次查询走的点数等于路径长度，最坏 ， 次查询合计 。 时是 量级，不可行。 - 空间：
。
瓶颈是查询本身：路径上的每一个点都要亲自走一遍、亲自判一次宗教。链状树上路径长度就是
解法一：树链剖分 + 按宗教拆分的动态开点线段树
思路
QS/QM x y 全程只关心
样例初始状态按宗教拆开是这样的（
text
城市： 1 3 4 5 2
dfn 位置： 1 2 3 4 5
评级： 3 1 3 5 2
宗教： 1 2 3 1 3
按宗教拆成三棵独立的线段树（下标仍是 dfn 位置）：
宗教 1 的树： [3] [ ] [ ] [5] [ ]
宗教 2 的树： [ ] [1] [ ] [ ] [ ]
宗教 3 的树： [ ] [ ] [3] [ ] [2]同一个 dfn 位置只在一棵树上取得到值——它在哪棵树的哪片叶子上，就代表那个城市当前属于哪个宗教。于是「查路径上宗教 CC 3 1 之后，评级
第一个障碍是空间：宗教数 int 也有 160 GB，而限制是 512 MiB。可是任意时刻只有
这里有一个容易算错的地方：不能拿「当前只有
- 初始化：
次插入，每次新建一条从根到叶的路径。 时树高不超过 ，路径上最多 个节点，合计不超过 。 CW：这个 dfn 位置早就在本宗教树里，路径已经存在，一个节点都不新建。CC：在旧树上清走的是已有路径，不新建；往新树写入时，若该 dfn 在这棵树里还没有路径，最多新建 个。
于是整个过程新建的节点总数不超过
这就是 MAXNODE = 4000005 的来历。如果只按「当前 CC 的数据上会低估一半，节点池直接越界。
四个操作因此各自落在很明确的位置上：
| 操作 | 做法 |
|---|---|
CC x c |
在旧宗教树上把 dfn[x] 一叶清 col[x]，在新宗教树上把 dfn[x] 写成 |
CW x w |
改 |
QS x y |
HLD 拆成 roots[col[x]] 上查区间和，累加 |
QM x y |
同上，查区间最大值，取最大 |
实现上有两个必须写对的地方：
- 空节点
全局共享。 range_query一进来遇到node == 0就直接返回，表示这棵宗教树在这段区间里没有任何城市。评级是正整数，所以「空」既可以当成和、也可以当成最大值 ，两个都是安全的中性元。 point_set的根要传引用。 一个宗教第一次出现时roots[c] == 0，函数里边必须新建根节点并把编号写回roots[c]，否则后续所有操作都找不到这棵树。
代码
代码按 rbook 模板 hld（全局数组、两次 DFS）与 segtree-dynamic（节点池 + 引用传根的动态线段树）组织；模板的剖分部分用显式栈避免链形树递归，这里因为
cpp
/**
* 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-08-12 22:59
* update_at: 2026-10-23 21:00
*/
// main.cpp：树链剖分 + 每种宗教一棵动态开点线段树。
// 把路径查询按宗教过滤：只统计路径上同宗教城市的评级和 / 最大值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXNODE = 4000005; // 初始 N 次与至多 Q 次改宗教插入，每次至多 18 个节点
int n, q;
int w[MAXN]; // w[i] 城市 i 的评级
int col[MAXN]; // col[i] 城市 i 的宗教
vector<int> g[MAXN]; // 树的邻接表
// ---- 树链剖分相关 ----
int parent[MAXN]; // 父亲
int depth[MAXN]; // 深度
int sz[MAXN]; // 子树大小
int heavy[MAXN]; // 重儿子
int top[MAXN]; // 重链链头
int dfn[MAXN]; // 剖分后的新编号（连续编号）
int timer; // dfn 计数器
// 第一次 dfs：计算 parent、depth、sz、heavy。
void dfs1(int u, int f) {
parent[u] = f;
depth[u] = depth[f] + 1;
sz[u] = 1;
heavy[u] = 0;
for (int v : g[u]) {
if (v == f) continue;
dfs1(v, u);
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
// 第二次 dfs：先走重儿子让重链编号连续，再开新链。
void dfs2(int u, int chain_top) {
top[u] = chain_top;
dfn[u] = ++timer;
if (heavy[u] != 0) {
dfs2(heavy[u], chain_top);
}
for (int v : g[u]) {
if (v == parent[u] || v == heavy[u]) continue;
dfs2(v, v);
}
}
// ---- 动态开点线段树（每种宗教一棵，共享节点池） ----
int lc[MAXNODE]; // 左儿子，0 表示空节点
int rc[MAXNODE]; // 右儿子，0 表示空节点
int seg_sum[MAXNODE]; // 区间和
int seg_max[MAXNODE]; // 区间最大值
int cnt; // 已使用的节点个数
int roots[MAXN]; // roots[c] 宗教 c 的线段树根
// 新建一个节点，返回节点编号。
int new_node() {
cnt++;
return cnt;
}
// 在 root 为根的线段树中把位置 pos 的叶子设为 val，并回溯更新祖先。
// root 传引用，因为新建根时要把新根写回。
void point_set(int &root, int l, int r, int pos, int val) {
if (root == 0) {
root = new_node();
}
if (l == r) {
seg_sum[root] = val;
seg_max[root] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
point_set(lc[root], l, mid, pos, val);
} else {
point_set(rc[root], mid + 1, r, pos, val);
}
seg_sum[root] = seg_sum[lc[root]] + seg_sum[rc[root]];
seg_max[root] = max(seg_max[lc[root]], seg_max[rc[root]]);
}
// 在 node 上查询区间 [ql, qr] 的和与最大值，结果累加到 tsum / tmax。
// 空节点（node == 0）表示这段区间内没有任何该宗教的城市，直接返回。
void range_query(int node, int l, int r, int ql, int qr, int &tsum, int &tmax) {
if (node == 0) {
return;
}
if (ql <= l && r <= qr) {
tsum += seg_sum[node];
tmax = max(tmax, seg_max[node]);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
range_query(lc[node], l, mid, ql, qr, tsum, tmax);
}
if (qr > mid) {
range_query(rc[node], mid + 1, r, ql, qr, tsum, tmax);
}
}
// 在宗教 rel 的线段树上查询路径 x -> y 的评级和与最大值。
void path_query(int x, int y, int rel, int &tsum, int &tmax) {
int root = roots[rel];
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
range_query(root, 1, n, dfn[top[x]], dfn[x], tsum, tmax);
x = parent[top[x]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
range_query(root, 1, n, dfn[x], dfn[y], tsum, tmax);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> col[i];
}
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 1);
// 初始：把每个城市按宗教插入对应的线段树。
for (int i = 1; i <= n; i++) {
point_set(roots[col[i]], 1, n, dfn[i], w[i]);
}
while (q--) {
string op;
int x, y;
cin >> op >> x >> y;
if (op == "CC") {
// 从旧宗教树中删除（叶子置 0），再插入新宗教树。
point_set(roots[col[x]], 1, n, dfn[x], 0);
col[x] = y;
point_set(roots[col[x]], 1, n, dfn[x], w[x]);
} else if (op == "CW") {
w[x] = y;
point_set(roots[col[x]], 1, n, dfn[x], y);
} else {
int tsum = 0, tmax = 0;
path_query(x, y, col[x], tsum, tmax);
if (op == "QS") {
cout << tsum << '\n';
} else {
cout << tmax << '\n';
}
}
}
return 0;
}同一个算法的 Python 实现放在 main.py，结构与 C++ 版本一一对应，用来对照阅读（range_query 改成了返回二元组、dfs2 改成显式栈）。它的常数更大，
python
import sys
from array import array
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
weight = [0] * (n + 1)
color = [0] * (n + 1)
for node in range(1, n + 1):
weight[node], color[node] = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = [1]
for node in order:
for neighbor in graph[node]:
if neighbor != parent[node]:
parent[neighbor] = node
depth[neighbor] = depth[node] + 1
order.append(neighbor)
subtree = [1] * (n + 1)
subtree[0] = 0
heavy = [0] * (n + 1)
for node in reversed(order[1:]):
subtree[parent[node]] += subtree[node]
if subtree[node] > subtree[heavy[parent[node]]]:
heavy[parent[node]] = node
top = [0] * (n + 1)
dfn = [0] * (n + 1)
timer = 0
chains = [(1, 1)]
while chains:
node, chain_top = chains.pop()
while node:
top[node] = chain_top
timer += 1
dfn[node] = timer
for neighbor in graph[node]:
if neighbor != parent[node] and neighbor != heavy[node]:
chains.append((neighbor, neighbor))
node = heavy[node]
# Node 0 is the shared empty node. Each religion owns one root in the same
# dynamic segment-tree pool.
left_child = array("i", [0])
right_child = array("i", [0])
node_sum = array("q", [0])
node_max = array("i", [0])
roots = array("i", [0]) * 100_001
def new_node():
left_child.append(0)
right_child.append(0)
node_sum.append(0)
node_max.append(0)
return len(left_child) - 1
def point_set(root, position, value):
if root == 0:
root = new_node()
node = root
left, right = 1, n
path = []
while left < right:
path.append(node)
middle = (left + right) // 2
if position <= middle:
if left_child[node] == 0:
left_child[node] = new_node()
node = left_child[node]
right = middle
else:
if right_child[node] == 0:
right_child[node] = new_node()
node = right_child[node]
left = middle + 1
node_sum[node] = value
node_max[node] = value
for node in reversed(path):
node_sum[node] = node_sum[left_child[node]] + node_sum[right_child[node]]
node_max[node] = max(node_max[left_child[node]], node_max[right_child[node]])
return root
def range_query(node, left, right, query_left, query_right):
if node == 0:
return 0, 0
if query_left <= left and right <= query_right:
return node_sum[node], node_max[node]
middle = (left + right) // 2
total = maximum = 0
if query_left <= middle:
total, maximum = range_query(left_child[node], left, middle, query_left, query_right)
if middle < query_right:
right_sum, right_max = range_query(right_child[node], middle + 1, right, query_left, query_right)
total += right_sum
maximum = max(maximum, right_max)
return total, maximum
for node in range(1, n + 1):
roots[color[node]] = point_set(roots[color[node]], dfn[node], weight[node])
def path_query(x, y, religion):
total = maximum = 0
root = roots[religion]
while top[x] != top[y]:
if depth[top[x]] < depth[top[y]]:
x, y = y, x
part_sum, part_max = range_query(root, 1, n, dfn[top[x]], dfn[x])
total += part_sum
maximum = max(maximum, part_max)
x = parent[top[x]]
if depth[x] > depth[y]:
x, y = y, x
part_sum, part_max = range_query(root, 1, n, dfn[x], dfn[y])
return total + part_sum, max(maximum, part_max)
answers = []
for _ in range(operations):
operation, x, value = input().split()
x, value = int(x), int(value)
if operation == b'CC':
roots[color[x]] = point_set(roots[color[x]], dfn[x], 0)
color[x] = value
roots[color[x]] = point_set(roots[color[x]], dfn[x], weight[x])
elif operation == b'CW':
weight[x] = value
roots[color[x]] = point_set(roots[color[x]], dfn[x], value)
else:
total, maximum = path_query(x, value, color[x])
answers.append(str(total if operation == b'QS' else maximum))
print("\n".join(answers))复杂度
- 预处理：两次 DFS
； 次初始插入，每次 ，合计 。 CC：两次单点写入； CW：一次单点写入。 QS/QM：路径拆成段，每段在宗教树上做一次区间查询 ，合计 。 - 空间：树剖数组
；节点池 ，上界 （推导见上文「思路」）， 时约 个节点，四个 int数组约 58 MiB，实测峰值 61 MiB。
-O2、cin 关闭同步、含读入，限制 1000 ms / 512 MiB）：随机树、链、菊花、完全二叉树、全 CC、全查询六组数据在 169–293 ms 之间；最坏的一组是「全同宗教 + 完全二叉树 + 叶子互查」，350 ms、21 MiB。峰值内存 61 MiB 出现在全 CC 那组，与节点池只增不减相符。
解法二：离线离散化 + 每个宗教一棵普通线段树
思路
解法一的空间浪费来自「为还没出现的位置预留节点」。如果能把每种宗教的坐标空间压到它真正可能出现的那些 dfn 上，普通线段树就够了，连动态开点都不需要。
未来是已知的：题目把所有操作一次性给出，没有加密、没有交互。于是先读入全部操作，模拟一遍宗教变更，就能收集到「宗教 CC 最多给新宗教增加一个位置，所以
也就是所有宗教树的节点总数不超过
剩下的问题是「dfn 值 → 该宗教内部的下标」。这个映射用一次二分就能完成：在 pos[c] 上 lower_bound。
路径查询也照旧拆段，只是每段多一步转换：dfn 区间
代价有两个，都很实际：
- 必须离线。要先把全部操作读进来才能知道每棵树的坐标表。如果题目改成强制在线（比如操作依赖上一次答案），这条路直接失效，只能回到解法一。
- 每次操作多一次二分。dfn 换成内部下标是
，与线段树的 同阶，实测差别不大。初始化也多了一步：排序去重所有宗教的坐标表，合计 。
CC 与 CW 的语义和边界（空位置、成对清除）与解法一相同，只是「清 0」变成了「往坐标表里定位再覆盖」。
代码
cpp
/**
* 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-30 07:51
* update_at: 2026-10-30 07:51
*/
// main2.cpp：解法二 —— 离线读入所有操作，把「每个宗教历史上出现过的 dfn」离散化，
// 于是每种宗教都能用一棵普通（静态数组）线段树，节点总数 O(n + q)，完全不用动态开点。
// 代价是要先把全部操作读进来，并多做一次 dfn -> 该宗教内部下标的映射。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXC = 100005; // 宗教编号上限
int n, q;
int w[MAXN]; // w[i]：城市 i 的评级
int col[MAXN]; // col[i]：城市 i 的宗教
vector<int> g[MAXN]; // 树的邻接表
// ---- 树链剖分 ----
int parent_[MAXN]; // parent_[u]：u 的父亲
int depth[MAXN]; // depth[u]：u 的深度（根为 1）
int sz[MAXN]; // sz[u]：u 的子树大小
int heavy[MAXN]; // heavy[u]：u 的重儿子，0 表示没有
int top[MAXN]; // top[u]：u 所在重链的链头
int dfn[MAXN]; // dfn[u]：u 剖分后的编号
int timer; // dfn 计数器
// 一次操作：type 是 CC / CW / QS / QM，x 是城市，y 是参数（宗教 / 评级 / 终点）
struct Op {
char type[3];
int x;
int y;
};
Op ops[MAXN]; // ops[i]：第 i 条操作
int cur[MAXN]; // cur[i]：离线模拟时城市 i 当前的宗教
// 每种宗教的离散化坐标：pos[c] 是宗教 c 历史上的所有 dfn，升序去重
vector<int> pos[MAXN];
int base[MAXN]; // base[c]：宗教 c 的线段树在池里的起点
int kcnt[MAXN]; // kcnt[c]：宗教 c 的坐标个数，线段树下标是 1..kcnt[c]
vector<int> seg_sum; // 节点池：区间和
vector<int> seg_max; // 节点池：区间最大值
// 第一次 dfs：求父亲、深度、子树大小、重儿子。
void dfs1(int u, int f) {
parent_[u] = f;
depth[u] = depth[f] + 1;
sz[u] = 1;
heavy[u] = 0;
for (auto v : g[u]) {
if (v == f) {
continue;
}
dfs1(v, u);
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
// 第二次 dfs：先走重儿子，让每条重链的 dfn 连续。
void dfs2(int u, int chain_top) {
top[u] = chain_top;
dfn[u] = ++timer;
if (heavy[u] != 0) {
dfs2(heavy[u], chain_top);
}
for (auto v : g[u]) {
if (v == parent_[u] || v == heavy[u]) {
continue;
}
dfs2(v, v);
}
}
// 把宗教 c 的第 idx 个坐标写成 val（val 为 0 表示清除）。
void point_set(int c, int node, int l, int r, int idx, int val) {
int p = base[c] + node;
if (l == r) {
seg_sum[p] = val;
seg_max[p] = val;
return;
}
int mid = (l + r) >> 1;
if (idx <= mid) {
point_set(c, node << 1, l, mid, idx, val);
} else {
point_set(c, node << 1 | 1, mid + 1, r, idx, val);
}
int lp = base[c] + (node << 1);
int rp = lp + 1;
seg_sum[p] = seg_sum[lp] + seg_sum[rp];
seg_max[p] = max(seg_max[lp], seg_max[rp]);
}
// 在宗教 c 的线段树上查内部下标区间 [ql, qr] 的和与最大值。
void range_query(int c, int node, int l, int r, int ql, int qr, int &tsum, int &tmax) {
if (ql <= l && r <= qr) {
int p = base[c] + node;
tsum += seg_sum[p];
tmax = max(tmax, seg_max[p]);
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
range_query(c, node << 1, l, mid, ql, qr, tsum, tmax);
}
if (qr > mid) {
range_query(c, node << 1 | 1, mid + 1, r, ql, qr, tsum, tmax);
}
}
// 把 dfn 值 d 在宗教 c 的坐标表里定位成内部下标；不在表里返回 0。
int find_index(int c, int d) {
int p = lower_bound(pos[c].begin(), pos[c].end(), d) - pos[c].begin();
if (p == (int)pos[c].size() || pos[c][p] != d) {
return 0;
}
return p + 1;
}
// 在宗教 rel 的树上前缀查询路径 x -> y：先按 HLD 拆段，每段再换成内部下标区间。
void path_query(int x, int y, int rel, int &tsum, int &tmax) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
int l = lower_bound(pos[rel].begin(), pos[rel].end(), dfn[top[x]]) - pos[rel].begin() + 1;
int r = upper_bound(pos[rel].begin(), pos[rel].end(), dfn[x]) - pos[rel].begin();
if (l <= r) {
range_query(rel, 1, 1, kcnt[rel], l, r, tsum, tmax);
}
x = parent_[top[x]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
int l = lower_bound(pos[rel].begin(), pos[rel].end(), dfn[x]) - pos[rel].begin() + 1;
int r = upper_bound(pos[rel].begin(), pos[rel].end(), dfn[y]) - pos[rel].begin();
if (l <= r) {
range_query(rel, 1, 1, kcnt[rel], l, r, tsum, tmax);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> col[i];
}
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= q; i++) {
cin >> ops[i].type >> ops[i].x >> ops[i].y;
}
dfs1(1, 0);
dfs2(1, 1);
// 第一遍离线：按当前宗教把每个城市可能出现过的 dfn 收集起来。
for (int i = 1; i <= n; i++) {
cur[i] = col[i];
pos[cur[i]].push_back(dfn[i]);
}
for (int i = 1; i <= q; i++) {
if (ops[i].type[0] == 'C' && ops[i].type[1] == 'C') {
cur[ops[i].x] = ops[i].y;
pos[cur[ops[i].x]].push_back(dfn[ops[i].x]);
}
}
// 每个宗教排序去重、分配一段连续节点池
int used = 0;
for (int c = 1; c < MAXC; c++) {
if (pos[c].empty()) {
continue;
}
sort(pos[c].begin(), pos[c].end());
pos[c].erase(unique(pos[c].begin(), pos[c].end()), pos[c].end());
kcnt[c] = (int)pos[c].size();
base[c] = used;
used += 4 * kcnt[c] + 4; // 普通线段树开 4 倍大小
}
seg_sum.assign(used, 0);
seg_max.assign(used, 0);
// 初始状态：把每个城市的评级写进它宗教树里对应的坐标
for (int i = 1; i <= n; i++) {
point_set(col[i], 1, 1, kcnt[col[i]], find_index(col[i], dfn[i]), w[i]);
}
// 第二遍在线：按顺序处理操作
for (int i = 1; i <= q; i++) {
int x = ops[i].x;
int y = ops[i].y;
char t0 = ops[i].type[0];
char t1 = ops[i].type[1];
if (t0 == 'C' && t1 == 'C') {
int c = col[x];
point_set(c, 1, 1, kcnt[c], find_index(c, dfn[x]), 0);
col[x] = y;
point_set(y, 1, 1, kcnt[y], find_index(y, dfn[x]), w[x]);
} else if (t0 == 'C') {
w[x] = y;
int c = col[x];
point_set(c, 1, 1, kcnt[c], find_index(c, dfn[x]), y);
} else {
int tsum = 0;
int tmax = 0;
path_query(x, y, col[x], tsum, tmax);
if (t0 == 'Q' && t1 == 'S') {
cout << tsum << '\n';
} else {
cout << tmax << '\n';
}
}
}
return 0;
}复杂度
- 预处理：两次 DFS
；离线模拟收集坐标 ；排序去重 ； 次初始插入 。 CC：两次「定位 + 单点写入」，每次； CW：一次定位 + 一次单点写入，。 QS/QM：段，每段一次二分 + 一次区间查询， 。 - 空间：树剖数组与坐标表
；节点池 。
实测同样是六组
解法三：一棵 dfn 线段树 + 每个节点挂宗教映射
思路
前两个解法都在「按宗教拆树」。换个方向想：树不拆，只在每个线段树节点上额外记一维「宗教 → 摘要」，也就是给每个节点挂一张 map。
text
dfn 线段树的每个节点各自持有一张「宗教 -> (和, 最大值)」的表：
[1,5]
┌──────────┴──────────┐
[1,3] [4,5]
┌───┴───┐ ┌───┴───┐
[1,2] [3,3] [4,4] [5,5]
节点 [1,2] 的表：{ 宗教1: (3, 3) } 节点 [4,5] 的表：{ 宗教1: (5, 5), 宗教3: (2, 2) }
节点 [1,5] 的表：{ 宗教1: (8, 5), 宗教2: (1, 1), 宗教3: (2, 2) }这样一来：
- 单点写：叶子节点上把宗教
的项设成 （清 0 就是删掉这一项），回溯时只需要重算宗教 这一项——别的宗教没被改过，不必动。 - 区间查询：区间拆成
个整节点，每个节点查一次 map取该宗教的摘要，把和相加、最大值取。某个节点上没有该宗教的项，就等价于空，贡献 。
写法确实最短：没有节点池，没有坐标映射，也没有「空节点」这种特殊情况——map 里没有这一项就是空。
但代价很直接。一次查询要访问 map 查找。而每个节点各持一张 map，map 对象加
代码
cpp
/**
* 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-30 07:51
* update_at: 2026-10-30 07:51
*/
// main3.cpp：解法三 —— 只开一棵 dfn 线段树，每个节点挂一个 map：宗教 -> (区间内该宗教的评级和, 最大值)。
// 不用树链剖分以外的任何技巧，路径查询照旧拆段，只是「按宗教过滤」交给每个节点上的 map。
// 写法最短，但每个节点一次 map 查找都要 O(log C)，常数和内存都比前两个解法大。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXC = 100005;
int n, q;
int w[MAXN]; // w[i]：城市 i 的评级
int col[MAXN]; // col[i]：城市 i 的宗教
vector<int> g[MAXN]; // 树的邻接表
// ---- 树链剖分 ----
int parent_[MAXN]; // parent_[u]：u 的父亲
int depth[MAXN]; // depth[u]：u 的深度（根为 1）
int sz[MAXN]; // sz[u]：u 的子树大小
int heavy[MAXN]; // heavy[u]：u 的重儿子
int top[MAXN]; // top[u]：u 所在重链的链头
int dfn[MAXN]; // dfn[u]：u 剖分后的编号
int timer; // dfn 计数器
// 一个节点里，某个宗教的摘要
struct Info {
int sum; // 该宗教在这些位置上的评级和
int mx; // 该宗教在这些位置上的评级最大值
};
map<int, Info> node_of_color[MAXN << 2]; // node_of_color[p]：节点 p 的区间里「宗教 -> 摘要」
void dfs1(int u, int f) {
parent_[u] = f;
depth[u] = depth[f] + 1;
sz[u] = 1;
heavy[u] = 0;
for (auto v : g[u]) {
if (v == f) {
continue;
}
dfs1(v, u);
sz[u] += sz[v];
if (heavy[u] == 0 || sz[v] > sz[heavy[u]]) {
heavy[u] = v;
}
}
}
void dfs2(int u, int chain_top) {
top[u] = chain_top;
dfn[u] = ++timer;
if (heavy[u] != 0) {
dfs2(heavy[u], chain_top);
}
for (auto v : g[u]) {
if (v == parent_[u] || v == heavy[u]) {
continue;
}
dfs2(v, v);
}
}
// 取节点 p 在宗教 c 上的和 / 最大值，没有该宗教就是 0。
int get_sum(int p, int c) {
auto it = node_of_color[p].find(c);
return it == node_of_color[p].end() ? 0 : it->second.sum;
}
int get_max(int p, int c) {
auto it = node_of_color[p].find(c);
return it == node_of_color[p].end() ? 0 : it->second.mx;
}
// 把位置 pos 上的宗教 c 的评级写成 val；val 为 0 表示这个位置不再属于宗教 c。
// 递归回来后只需要重算宗教 c 这一项，别的宗教没被改过。
void point_set(int p, int l, int r, int pos, int c, int val) {
if (l == r) {
if (val == 0) {
node_of_color[p].erase(c);
} else {
Info info;
info.sum = val;
info.mx = val;
node_of_color[p][c] = info;
}
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) {
point_set(p << 1, l, mid, pos, c, val);
} else {
point_set(p << 1 | 1, mid + 1, r, pos, c, val);
}
int sum = get_sum(p << 1, c) + get_sum(p << 1 | 1, c);
if (sum == 0) {
node_of_color[p].erase(c); // 这个宗教在本节点的区间里已经空了
return;
}
Info info;
info.sum = sum;
info.mx = max(get_max(p << 1, c), get_max(p << 1 | 1, c));
node_of_color[p][c] = info;
}
// 在区间 [ql, qr] 里查宗教 c 的和与最大值。
void range_query(int p, int l, int r, int ql, int qr, int c, int &tsum, int &tmax) {
if (ql <= l && r <= qr) {
tsum += get_sum(p, c);
tmax = max(tmax, get_max(p, c));
return;
}
int mid = (l + r) >> 1;
if (ql <= mid) {
range_query(p << 1, l, mid, ql, qr, c, tsum, tmax);
}
if (qr > mid) {
range_query(p << 1 | 1, mid + 1, r, ql, qr, c, tsum, tmax);
}
}
// HLD 拆段后，每段都用宗教 rel 去查。
void path_query(int x, int y, int rel, int &tsum, int &tmax) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
range_query(1, 1, n, dfn[top[x]], dfn[x], rel, tsum, tmax);
x = parent_[top[x]];
}
if (depth[x] > depth[y]) {
swap(x, y);
}
range_query(1, 1, n, dfn[x], dfn[y], rel, tsum, tmax);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> col[i];
}
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1, 0);
dfs2(1, 1);
for (int i = 1; i <= n; i++) {
point_set(1, 1, n, dfn[i], col[i], w[i]);
}
while (q--) {
string op;
int x, y;
cin >> op >> x >> y;
if (op == "CC") {
point_set(1, 1, n, dfn[x], col[x], 0);
col[x] = y;
point_set(1, 1, n, dfn[x], col[x], w[x]);
} else if (op == "CW") {
w[x] = y;
point_set(1, 1, n, dfn[x], col[x], y);
} else {
int tsum = 0;
int tmax = 0;
path_query(x, y, col[x], tsum, tmax);
if (op == "QS") {
cout << tsum << '\n';
} else {
cout << tmax << '\n';
}
}
}
return 0;
}复杂度
- 预处理：
次单点写入，每次 ，合计 。 CC：两次单点写入； CW：一次。 QS/QM：个节点，每个节点一次 map查找，合计 。 - 空间：
个 map表项，约项，加上 个 map对象本身。
实测（同样六组 map 换成 unordered_map 能把常数压到 1.2–3.6 s，仍然超时——省掉的是
所以这个解法适合当「同一个模型的编码对照」：它说明动态开点 / 离线离散化省下来的到底是什么（不是算法复杂度，而是每次操作要碰的节点数和内存），但不宜作为正式提交。
复杂度对比
三个解法的实测都来自同一批数据：CC / 全查询六组，命令是 roj-local-judge-lite --time 1000 --memory 512。
| 指标 | 解法一（动态开点） | 解法二（离线离散化） | 解法三（单树 + map） |
|---|---|---|---|
| 时间 | 169–293 ms | 162–276 ms | 1.8–6.3 s（TLE） |
| 峰值内存 | 33–61 MiB | 20–28 MiB | 95–119 MiB |
| 是否要求离线 | 不要求 | 要求，先读完所有操作 | 不要求 |
| 代码量（行） | 178 | 231 | 190 |
| 主要风险 | 节点池上界要估准 | 离线前提；多一层二分 | 常数与内存都超预算 |
选法很简单：默认用解法一（在线、够快、代码最短之一）；如果题目本来就允许离线、又卡内存，解法二更划算；解法三当成理解「按宗教过滤」本质的中间形态，不作为提交方案。
总结
这道题的骨架是「一维路径区间化 + 第二维按宗教过滤」，前半段三种解法完全一样，差别全在第二维怎么落地：
- 树链剖分把路径变成
段 dfn 连续区间，解决「路径不是区间」这个障碍； - 解法一把第二维拆成很多棵树，用动态开点把空间压到
； - 解法二同样拆树，但用离线已知的操作把坐标空间压缩成
，于是普通线段树就够，内存还更省； - 解法三不拆树，把第二维放进每个节点的
map，写法最短，代价是每次操作要碰个节点、每个节点再查一次 map。
两个操作语义值得单独记住：CC 是「一清一写」，相当于在两个集合之间搬家；CW 是单点覆盖。它们都只碰
图示解析
下面这张 ASCII 图串起暴力和三条解法，标出每一步消除的瓶颈。
text
暴力（brute.cpp）
定根后让较深的一端向上爬，逐点判断宗教、累加评级
单次查询 O(路径长)，总计 O(n*m)
|
| 共同的第一步：路径上的点要一个一个走
v
树链剖分（三个解法共用）
两次 DFS 求重儿子与链头，按 dfn 重编号
任意路径 = O(log n) 段 dfn 连续区间
|
| 剩下的事：区间里混着各种宗教，怎么只统计其中一种
+------------------------+-------------------------+
v v v
解法一：按宗教拆树 解法二：拆树 + 离线压缩 解法三：不拆树
每宗教一棵树，共享节点池 每宗教一棵普通树 单棵 dfn 线段树
动态开点，O((n+m)log n) 坐标为历史 dfn，O(n+m) 每节点挂 map<宗教, 摘要>
CC/CW O(log n) CC/CW O(log n) CC/CW O(log n log C)
QS/QM O(log^2 n) QS/QM O(log^2 n) QS/QM O(log^2 n log C)
169-293 ms, 33-61 MiB 162-276 ms, 20-28 MiB 1.8-6.3 s, 95-119 MiB图中三处分支比较的是同一件事的三种落地方式。解法一和解法二的差别只有「坐标空间从哪来」（在线开点 vs 离线压缩），所以时间同级、内存差一倍；解法三把过滤搬进节点内部，省掉了拆树，却让每次操作多乘一个
参考与致谢
下列公开题解提供了本文所比较的解法思路来源；本文未复用其原文或代码。题目建模说明、边界论证、三个解法的代码和验证由本文独立整理。
| 作者与题解 | 来自原题解 | 本文独立补充 |
|---|---|---|
| Fading（uid 20309），题解 P3313 【[SDOI2014]旅行】 | 按宗教分组维护动态开点线段树，并用树链剖分处理路径 | 重新说明共享空节点、赋值式修改与路径拆分的适用条件；解法一代码独立实现 |
| Link_Cut_Y（uid 519384），P3313 [SDOI2014] 旅行 题解 | 提供按树剖序分块的替代路线及块长讨论 | 核查其数组维度和实际内存开销，指出此处所示实现不宜作为较简单主解 |
| 斯德哥尔摩（uid 49998），题解 P3313 【[SDOI2014]旅行】 | 按宗教分别维护动态线段树，并在路径分段后查询 | 补充分析其节点池开销与操作语义，独立复核主路线 |
| 喵仔牛奶（uid 560516），P3313 [SDOI2014]旅行分块题解 | 分块摘要维护各宗教在块内的和与最大值 | 对照其二维数组的最坏容量，说明实现空间不适合作为本题短小主解 |
| 半仙胡小桃（uid 19842），题解 P3313 【[SDOI2014]旅行】 | 树链剖分配合按宗教动态线段树 | 本文独立解释每个操作如何映射到点覆盖和区间摘要，不沿用代码 |
解法二（离线离散化）与解法三（节点挂 map）是本文按「能不能不开点」「能不能不拆树」两个方向自行推导并实现的对照方案，未参考上述题解。