【模板】重链剖分 / 树链剖分

形式化题目

思路

代码

复杂度

总结

图示解析

样例的链剖分

数学视角：为什么拆段 + 懒标记能成立

给定一棵 $n$ 个节点的带权树，根为 $r$ ，所有结果对 $P$ 取模。依次执行 $m$ 次操作：

路径加： $x$ 到 $y$ 最短路径上所有点权加 $z$ ；
路径和：输出 $x$ 到 $y$ 最短路径上所有点权之和；
子树加：以 $x$ 为根的子树内所有点权加 $z$ ；
子树和：输出以 $x$ 为根的子树内所有点权之和。

本质上是要在一棵树上支持"一条路径"与"一棵子树"这两种点集的区间加与区间和。

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

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/**
 * 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:29
 * update_at: 2026-08-12 22:34
 */
// brute.cpp：小数据暴力解，路径操作沿父链一步一步爬，子树操作 DFS 枚举，
// 用来帮助理解题意并辅助对拍。只适合 n 很小的情况。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m, root;
long long mod;
long long a[MAXN];          // a[i] 表示节点 i 当前的权值（始终对 mod 取模）
int fa[MAXN];               // fa[i] 表示节点 i 的父亲
int depth[MAXN];            // depth[i] 表示节点 i 的深度
vector<int> g[MAXN];        // 邻接表存树

// 从根出发 BFS，求出每个节点的父亲和深度。
void build_parent() {
    queue<int> q;
    q.push(root);
    fa[root] = 0;
    depth[root] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa[u]) continue;
            fa[v] = u;
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }
}

// 路径加：让 x、y 中较深的一个先向上爬，直到两点相遇，
// 途中经过的每个点都加 z（沿父链爬，单次操作 O(深度)）。
void path_add(int x, int y, long long z) {
    while (x != y) {
        if (depth[x] < depth[y]) swap(x, y);
        a[x] = (a[x] + z) % mod;
        x = fa[x];
    }
    a[x] = (a[x] + z) % mod;
}

// 路径和：和路径加同样的爬法，把沿途经过的点的权值累加起来。
long long path_sum(int x, int y) {
    long long answer = 0;
    while (x != y) {
        if (depth[x] < depth[y]) swap(x, y);
        answer = (answer + a[x]) % mod;
        x = fa[x];
    }
    answer = (answer + a[x]) % mod;
    return answer;
}

// 子树加：DFS 枚举 u 子树内每个节点，逐个加 z。
void subtree_add(int u, int father, long long z) {
    a[u] = (a[u] + z) % mod;
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == father) continue;
        subtree_add(v, u, z);
    }
}

// 子树和：DFS 枚举 u 子树内每个节点，逐个累加。
long long subtree_sum(int u, int father) {
    long long answer = a[u];
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        if (v == father) continue;
        answer = (answer + subtree_sum(v, u)) % mod;
    }
    return answer;
}

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

    cin >> n >> m >> root >> mod;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= mod;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_parent();

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            long long z;
            cin >> x >> y >> z;
            path_add(x, y, z % mod);
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            cout << path_sum(x, y) << '\n';
        } else if (op == 3) {
            int x;
            long long z;
            cin >> x >> z;
            // 以 fa[x] 作为"不要进入的节点"，保证只枚举 x 的子树。
            subtree_add(x, fa[x], z % mod);
        } else {
            int x;
            cin >> x;
            cout << subtree_sum(x, fa[x]) << '\n';
        }
    }

    return 0;
}

brute.cpp 的思路是最直接的：路径操作让较深的点沿父亲链一步一步爬，相遇即覆盖整条路径，逐点加或逐点求和；子树操作 DFS 枚举子树内所有点。单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。

瓶颈很清楚：点集有多大，就要访问多少个点。树上的路径和子树都没有数组那样的"连续区间"表示，无法跳过中间节点整体结算。

关键观察是重新编号：用两遍 DFS 给每个点分配新编号 dfn，让两类点集都变成连续区间：

子树天然是连续区间：任意 DFS 序下，以 $u$ 为根的子树内的点占据区间 $[\text{dfn}[u],\ \text{dfn}[u] + \text{size}[u] - 1]$ ，这是 DFS 序的普通性质。
路径可以拆成 $O(\log n)$ 段：DFS 编号时优先走重儿子（子树最大的儿子）。从链头沿重儿子一路走到的点编号连续，形成一条"重链"；路径上每跨一条轻边，子树大小至少翻倍，所以轻边最多 $\log_2 n$ 条，任意路径最多拆成 $O(\log n)$ 条重链上的连续段。

这样四种操作统一退化为线段树的两个原语"区间加、区间和"，由懒标记在 $O(\log n)$ 内完成（P3870 已经建立过 apply / push 的懒标记模型，本题只是把"翻转"换成"加值"）。

下面这张图展示样例树（ $n=5,\ r=2$ ，括号内是 dfn 编号）的重链与编号结果：

text

1
2
3
4
5       2 (1)
       |
       1 (2) ── 5 (3)     重链：2-1-5，dfn 连续 1,2,3
      / \
   3 (4)  4 (5)           轻儿子 3、4 各自开新链

观察两个连续性质：重链 2-1-5 的编号是连续的 1,2,3；子树 1 覆盖编号区间 [2,5]，恰好包含 1,5,3,4 四个节点。路径 1 → 3 被拆成两段：先在重链上处理段 [2,2]，跨一条轻边后处理段 [4,4]，两次区间操作即可完成。

把上面的结构用代数语言压缩：

查询信息构成幺半群：区间和用 $+$ 合并，构成幺半群 $(\mathbb{Z}, +, 0)$ 。
区间加是摘要上的自同态：整段加 $v$ 后，区间和只需 $O(1)$ 更新为 $\text{sum} + v \cdot \text{len}$ ，可以在节点摘要上整体结算，不需要下到叶子——这正是 P3870 懒标记成立的条件，把"翻转"替换为"加值"即可。
HLD 提供的是"点集 → 区间"映射：子树与重链段都映射为连续区间，于是路径操作退化为若干次区间操作，线段树可以逐段结算。

以下表为样例操作过程，验证四种操作如何累积：

观察表中两次子树加：3 4 2 只改点 4（区间 [5,5]），3 2 2 改整棵树（区间 [1,5]），这正是 "子树 → dfn 连续区间"的体现；最后 2 1 3 沿路径 1→3 累加 12 + 9 = 21，与样例输出一致。

实现上，main.cpp 与 rbook 模板 hld 接口一致：dfs_size 求父亲、深度、子树大小、重儿子； dfs_decompose 先重后轻分配 dfn 并记录链头 top；path_add / path_sum 用 while (top[x] != top[y]) 逐段处理"链头更深一侧的整段"，subtree_add / subtree_sum 直接处理连续区间 [dfn[x], dfn[x] + size[x] - 1]。

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/**
 * 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:29
 * update_at: 2026-08-12 22:29
 */
#include <bits/stdc++.h>
using namespace std;

// ============ 线段树：区间加、区间和（带懒标记） ============
// 接口仿照 rbook 模板 hld 中的 SegmentTree。
struct SegmentTree {
    vector<long long> sum;   // sum[u] 节点 u 覆盖区间的和（已对 mod 取模）
    vector<long long> lazy;  // lazy[u] 节点 u 上欠着的"整段加"值
    int mod = 1;             // 题目给定的取模数 P

    SegmentTree(int n = 0, int mod_value = 1) {
        init(n, mod_value);
    }

    void init(int n, int mod_value) {
        mod = mod_value;
        sum.assign(n * 4 + 5, 0);
        lazy.assign(n * 4 + 5, 0);
    }

    // 给节点 u 的整个区间加上 value：区间和增加 value * 长度，标记也加上 value。
    void apply(int u, int l, int r, long long value) {
        value %= mod;
        sum[u] = (sum[u] + value * (r - l + 1)) % mod;
        lazy[u] = (lazy[u] + value) % mod;
    }

    // 把节点 u 的懒标记下传给两个儿子，之后 u 的标记清零。
    void pushdown(int u, int l, int r) {
        if (lazy[u] == 0 || l == r) return;
        int mid = (l + r) >> 1;
        apply(u << 1, l, mid, lazy[u]);
        apply(u << 1 | 1, mid + 1, r, lazy[u]);
        lazy[u] = 0;
    }

    // 用按 dfn 排列好的点权 base[1..n] 建树。
    void build(int u, int l, int r, const vector<long long> &base) {
        if (l == r) {
            sum[u] = base[l] % mod;
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, base);
        build(u << 1 | 1, mid + 1, r, base);
        sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % mod;
    }

    // 区间 [ql, qr] 每个数加 value。
    void range_add(int ql, int qr, long long value, int u, int l, int r) {
        if (ql <= l && r <= qr) {
            apply(u, l, r, value);
            return;
        }
        pushdown(u, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) range_add(ql, qr, value, u << 1, l, mid);
        if (qr > mid) range_add(ql, qr, value, u << 1 | 1, mid + 1, r);
        sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % mod;
    }

    // 询问区间 [ql, qr] 的和。
    long long range_sum(int ql, int qr, int u, int l, int r) {
        if (ql <= l && r <= qr) return sum[u];
        pushdown(u, l, r);
        int mid = (l + r) >> 1;
        long long answer = 0;
        if (ql <= mid) answer += range_sum(ql, qr, u << 1, l, mid);
        if (qr > mid) answer += range_sum(ql, qr, u << 1 | 1, mid + 1, r);
        return answer % mod;
    }
};

// ============ 重链剖分：两遍 DFS + 跳链路径操作 ============
// 接口仿照 rbook 模板 hld。
struct HeavyLightDecomposition {
    int n;
    int root;
    int mod;
    int timer = 0;              // dfn 计数器
    vector<vector<int>> graph;  // 邻接表存树
    vector<int> parent, depth, subtree_size, heavy_son;
    vector<int> top, dfn, node_at;
    vector<long long> value, ordered_value;  // 原树点权 / 按 dfn 排列后的点权
    SegmentTree seg;

    HeavyLightDecomposition(int n, int root, int mod)
        : n(n), root(root), mod(mod),
          graph(n + 1),
          parent(n + 1), depth(n + 1), subtree_size(n + 1),
          heavy_son(n + 1, 0), top(n + 1), dfn(n + 1), node_at(n + 1),
          value(n + 1), ordered_value(n + 1),
          seg(n, mod) {}

    void add_edge(int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 第一遍 DFS：求出 parent / depth / subtree_size / heavy_son（子树最大的儿子）。
    void dfs_size(int u, int father) {
        parent[u] = father;
        depth[u] = depth[father] + 1;
        subtree_size[u] = 1;
        heavy_son[u] = 0;

        for (int v : graph[u]) {
            if (v == father) continue;
            dfs_size(v, u);
            subtree_size[u] += subtree_size[v];
            if (heavy_son[u] == 0 ||
                subtree_size[v] > subtree_size[heavy_son[u]]) {
                heavy_son[u] = v;
            }
        }
    }

    // 第二遍 DFS：分配 dfn。优先走重儿子，让整条重链的编号连续。
    void dfs_decompose(int u, int chain_top) {
        top[u] = chain_top;      // u 所在重链的链头
        dfn[u] = ++timer;        // DFS 新编号
        node_at[timer] = u;
        ordered_value[timer] = value[u];

        if (heavy_son[u] != 0) {
            dfs_decompose(heavy_son[u], chain_top);
        }

        // 轻儿子各自开启一条新链。
        for (int v : graph[u]) {
            if (v == parent[u] || v == heavy_son[u]) continue;
            dfs_decompose(v, v);
        }
    }

    void build() {
        dfs_size(root, 0);
        dfs_decompose(root, root);
        seg.build(1, 1, n, ordered_value);
    }

    // 路径 (u, v) 上所有点加 delta：不断处理"更深一侧链头到当前点"这段，
    // 然后 u 跳到链头的父亲。两点的链头相同后，最后处理同一重链上的一段。
    void path_add(int u, int v, long long delta) {
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            seg.range_add(dfn[top[u]], dfn[u], delta, 1, 1, n);
            u = parent[top[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        seg.range_add(dfn[u], dfn[v], delta, 1, 1, n);
    }

    // 路径 (u, v) 上所有点的和。
    long long path_sum(int u, int v) {
        long long answer = 0;
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            answer += seg.range_sum(dfn[top[u]], dfn[u], 1, 1, n);
            answer %= mod;
            u = parent[top[u]];
        }
        if (depth[u] > depth[v]) swap(u, v);
        answer += seg.range_sum(dfn[u], dfn[v], 1, 1, n);
        return answer % mod;
    }

    // 子树操作不需要跳链：以 u 为根的子树就是 dfn 上的连续区间。
    void subtree_add(int u, long long delta) {
        seg.range_add(dfn[u], dfn[u] + subtree_size[u] - 1, delta, 1, 1, n);
    }

    long long subtree_sum(int u) {
        return seg.range_sum(dfn[u], dfn[u] + subtree_size[u] - 1, 1, 1, n);
    }
};

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

    int n, m, root, mod;
    cin >> n >> m >> root >> mod;

    HeavyLightDecomposition hld(n, root, mod);
    for (int i = 1; i <= n; i++) {
        cin >> hld.value[i];
        hld.value[i] %= mod;
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        hld.add_edge(u, v);
    }

    hld.build();

    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y;
            long long z;
            cin >> x >> y >> z;
            hld.path_add(x, y, z);
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            cout << hld.path_sum(x, y) << '\n';
        } else if (op == 3) {
            int x;
            long long z;
            cin >> x >> z;
            hld.subtree_add(x, z);
        } else {
            int x;
            cin >> x;
            cout << hld.subtree_sum(x) << '\n';
        }
    }

    return 0;
}

预处理（两遍 DFS + 建树）： $O(n)$ 。
子树加 / 子树和： $O(\log n)$ 。
路径加 / 路径和： $O(\log^2 n)$ （ $O(\log n)$ 段，每段线段树 $O(\log n)$ ）。
空间： $O(n)$ 。

重链剖分的本质是给树重新编号，把"路径"和"子树"这两种树上点集映射成 dfn 上的连续区间：子树一次区间操作，路径 $O(\log n)$ 次区间操作，剩下的区间加、区间和全部交给懒标记线段树。掌握接口后，树剖题的变化主要在于替换线段树维护的统计量。rbook 的《树链剖分》讲解了本解使用的模板（hld）：两遍 DFS + 跳链循环 + 线段树，本解即由该模板按本题输入输出改造而来。

3 4 2（子树 4 加 2）

3 2 2（子树 2 加 2）

1 5 1 3（路径 5-1 加 3）

2 1 3（路径 1-3 和）

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

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素模拟（brute.cpp）
  路径操作沿父亲链逐点爬，子树操作 DFS 逐点枚举   O(n) 每次操作
        |
        | 瓶颈：逐点访问，m 次操作 O(n*m) 太大
        v
关键观察（重新编号）
  子树 u -> dfn 区间 [dfn[u], dfn[u]+size[u]-1]
  重链 dfs 连续编号；路径拆成 O(log n) 条重链段（轻边让子树大小翻倍）
        |
        v
重链剖分 + 懒标记线段树（main.cpp）
  dfs_size    ：parent/depth/size/heavy（重儿子）
  dfs_decompose：先重后轻分配 dfn，记录链头 top
  路径操作：while (top[x] != top[y]) 处理整段 [dfn[top], dfn[x]] 后跳链
  子树操作：直接区间 [dfn[x], dfn[x]+size[x]-1]
  线段树：区间加 / 区间和，lazy 整段结算
        |
        v
复杂度 O(n) 预处理 + O(log n)（子树）/ O(log^2 n)（路径）每次操作

图中四条主线对应"暴力慢在哪"“编号如何让点集变成区间”“两遍 DFS 各自算什么”“四种操作如何映射到线段树”。核心是把"树上的路径"这个非序列对象，变成 $O(\log n)$ 个数组连续区间，难度就从逐点访问降为分段区间操作。