[SDOI2014] 旅行

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

树链剖分把路径拆成区间，按宗教拆成多棵动态开点线段树，只统计同宗教城市的评级和与最大值。

OJ: luogu

题目 ID: P3313

难度:提高+/省选-

标签:重链剖分动态线段树路径查询

日期: 2026-07-17 02:00

形式化题目

一棵 $n$ 个节点的树，每个节点 $i$ 有两个属性：宗教 $c_i$ 与评级 $w_i$ 。给出 $m$ 次操作，要求按顺序处理：

CC x c：把节点 $x$ 的宗教改为 $c$ ；
CW x w：把节点 $x$ 的评级改为 $w$ ；
QS x y：求路径 $x \to y$ 上宗教等于 $c_x$ 的节点评级之和（保证 $c_x = c_y$ ）；
QM x y：求路径 $x \to y$ 上宗教等于 $c_x$ 的节点评级最大值。

每次 QS / QM 输出一行答案。

思路

先看一个可以直接验证想法的朴素解：

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/**
 * 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;
}

brute.cpp 的 path_query 让较深的端点不断向上爬，逐点判断宗教是否与起点相同：每次查询都要把路径上的点全走一遍，链状树时单次 $O(n)$ ， $m$ 次操作总 $O(nm)$ ，无法通过 $10^5$ 的数据。

关键观察有三点：

路径可以变成区间：树链剖分把 $x \to y$ 拆成 $O(\log n)$ 段 dfn 连续区间（rbook《树链剖分》模板 hld）。
查询只关心一种宗教：QS/QM x y 全程只统计宗教 $c_x$ 的城市，这等价于"在一棵只含该宗教城市的树上做区间查询"。
每种宗教一棵线段树，但动态开点：宗教数 $C \leqslant 10^5$ ，每棵都建满 $4n$ 个节点不可能；但任意时刻所有城市加起来只有 $n$ 个"有值"位置，所以所有宗教树共享一个节点池、按需建点（节点池写法参考 rbook 模板 segtree-persistent-array）。

下面这张 ASCII 表展示样例初始状态被按宗教拆开后的样子。样例树的 HLD 编号（根为 1，重链 $1 \to 3 \to 4$ ）是：城市 $1,3,4,5,2$ 依次得到 dfn 位置 $1,2,3,4,5$ ：

text

1
2
3
4
5
6
7
8
9城市：         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 位置只在一棵树里有值——它在哪棵树的哪片叶子，就代表这个城市当前属于哪个宗教。于是 QS 1 5（宗教 1）就是"在宗教 1 的树上查路径 $1 \to 3 \to 5$ 拆出的区间"，命中位置 1 与 4 的评级 3 和 5，答案 8；CC 3 1 后城市 3 的评级 1 从宗教 2 的树挪进宗教 1 的树，再查就变成 $3+1+5=9$ ，与样例一致。

四个操作全部落在动态线段树上：

操作	做法
`CC x c`	旧宗教树叶子清 0，改 `col[x]`，新宗教树叶子写入 `w[x]`
`CW x w`	改 `w[x]`，当前宗教树叶子覆盖为 `w`
`QS/QM x y`	HLD 拆路径，每段区间在 `roots[col[x]]` 上查询，和相加、最大值取 max

实现上有两个关键点：

空节点 0 全局共享：range_query 遇到 node == 0 直接返回，表示该宗教在这段区间没有城市；评级恒为正整数，空区间的和 0、最大值 0 都是安全的中性元。
point_set 的根传引用：把城市移进一个从未出现过的宗教时 roots[c] == 0，函数里要新建根节点并写回 roots[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/**
 * 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
 */
// main.cpp：树链剖分 + 每种宗教一棵动态开点线段树。
// 把路径查询按宗教过滤：只统计路径上同宗教城市的评级和 / 最大值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXNODE = 4000005; // 动态线段树节点池大小：约 (N+Q) 次插入 * logN

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;
}

复杂度

预处理：两次树剖 DFS $O(n)$ ，初始 $n$ 次插入 $O(n \log n)$ 。
单点修改：CC / CW 各 $O(\log n)$ 。
路径查询：拆成 $O(\log n)$ 段、每段线段树 $O(\log n)$ ，共 $O(\log^2 n)$ 。
空间：树剖数组 $O(n)$ ；动态节点池最坏 $(N + Q)(\log n + 2)$ 个节点（只有首次进入一棵从未用过的宗教树才新建整条链），约 $3.6 \times 10^6$ 个，四个 int 数组约 58MB，在内存限制内。

总结

这道题的本质是"按第二维（宗教）把一维位置拆开"：树链剖分负责把路径区间化，按宗教拆分的动态线段树把"只统计同色点"的过滤直接内置进数据结构。改色 = 两棵树的叶子一清一写，改权 = 单叶覆盖，路径查询 = 在指定宗教树上做区间和与区间最大值。所有宗教共享一个节点池、空节点为 0 的写法让它空间上可行；这套"多维拆分 + 动态开点"的组合是省选难度题目的高频套路。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素模拟（brute.cpp）
  查询：x、y 逐点向上爬，逐点判断宗教是否相同     O(路径长) 每次查询
        |
        | 瓶颈：链状树路径长 O(n)，m 次查询总 O(nm)
        v
关键观察
  ① 路径 = O(log n) 段 dfn 连续区间（树链剖分）
  ② 查询只关心一种宗教 → 把位置按宗教拆开，每宗教一棵线段树
  ③ 所有宗教树共享节点池，动态开点，节点数 O((n+m)log n)
        |
        v
正式解（main.cpp）
  预处理：树剖两次 DFS，按宗教插入初始城市        O(n log n)
  改宗教：旧树叶子清 0，新树叶子写入 w[x]        O(log n)
  改评级：当前宗教树叶子覆盖写                    O(log n)
  查询：  HLD 拆路径，每段在 roots[rel] 上查       O(log^2 n)
        |
        v
复杂度：预处理 O(n log n)，单点 O(log n)，查询 O(log^2 n)

图中三条主线分别对应"暴力慢在哪里"“观察到什么性质”“正式解如何利用这些性质”。最值得记住的是中间那一步：路径被拆成区间之后，剩下的困难只剩"按宗教过滤"，而把每个宗教单独建一棵树、动态开点共享节点池，就把过滤问题变成了普通的区间求和与区间最大值。

P3313 [SDOI2014] 旅行

题目描述

S 国有 $N$ 个城市，编号从 $1$ 到 $N$ 。城市间用 $N-1$ 条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

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

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

CC x c：城市 $x$ 的居民全体改信了 $c$ 教；
CW x w：城市 $x$ 的评级调整为 $w$ ；
QS x y：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级总和；
QM x y：一位旅行者从城市 $x$ 出发，到城市 $y$ ，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $100\%$ 的数据， $N,Q \leq10^5,C \leq10^5$

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

[SDOI2014] 旅行

目录

形式化题目

思路

代码

复杂度

总结

图示解析