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

形式化题目

思路

代码

复杂度

总结

图示解析

样例的链剖分

为什么拆段与懒标记能够成立

给定一棵 $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$ 的数据。

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

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

子树天然是连续区间：任意 DFS 序下，以 $u$ 为根的子树内的点占据区间 $[\text{dfn}[u],\ \text{dfn}[u] + \text{sz}[u] - 1]$ ，这是 DFS 序的普通性质。
路径可以拆成 $O(\log n)$ 段：DFS 编号时优先走重儿子（子树最大的儿子）。从链头沿重儿子一路走到的点编号连续，形成一条“重链”。重儿子是子树最大的儿子，所以任何轻儿子 $v$ 都满足 $\text{sz}[v] \leqslant (\text{sz}[u] - 1) / 2$ ——否则 $v$ 就会是重儿子。也就是说每跨过一条轻边，子树大小至少翻倍，从任意点向上最多只能跨 $\log_2 n$ 条轻边，于是任意路径最多拆成 $O(\log n)$ 条重链上的连续段。

这样四种操作统一退化为线段树的两个基本操作“区间加、区间和”，由懒标记在 $O(\log n)$ 内完成（P3870 已经建立过 apply + push 的懒标记模型，本题把“翻转”换成“加值”，下发函数叫 pushdown）。

下图是样例树（ $n=5$ ，根 $r=2$ ）：粗蓝线是重边，灰虚线是轻边，每个点上方标出它分到的 dfn。

图下方把 dfn 数组按位置 1 到 5 排开，格子里是原节点编号。同一色的格子属于同一条重链，所以一眼能看出两条性质：重链 2-1-5 的编号连续为 1,2,3；子树 1 覆盖位置区间 [2,5]，恰好是 1,5,3,4 四个节点。

同一份数组上，路径和子树各自落到哪些位置，看第二张图：

路径 1 → 3 不是一段连续区间，它被拆成 [4,4]（点 3）和 [2,2]（点 1）两段，中间跨一条轻边；子树不拆段：子树 4 就是 [5,5]，子树 1 就是 [2,5]。四种操作因此全部归约为区间操作。

图里两个轻儿子的编号顺序是 3 在前、4 在后，这由 main.cpp 的遍历方式决定：build() 里 dfs2 先递归重儿子（拿到 dfn=3），再按邻接表顺序递归各个轻儿子，所以先遇到 3（dfn=4）、后遇到 4（dfn=5）。这个顺序完全由实现方式决定，不影响正确性——只要同一条重链的编号连续、子树仍是连续区间即可。

把上面的结构压缩成三条性质：

区间和可合并：两个不相交区间的点权和可以直接相加，合并运算满足结合律，单位元是 $0$ 。
区间加能在整段上结算：长度 $\text{len}$ 的区间每个点加 $v$ ，整段和只增加 $v \cdot \text{len}$ ，所以线段树节点可以在 $O(1)$ 内更新自己的和并打上懒标记，不必下到叶子——这正是 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 的全局数组加普通函数写法，没有结构体封装。模板把代码分成两段：sgt 段只维护数组 base[1..n] 上的区间加与区间和，hld 段负责把树上路径与子树翻译成 base 上的连续区间。两段共用 base：base[t] = a[rev[t]]，即按 dfn 重排后的点权。

n 和 mod 直接在 main 里读入，不需要额外的 init。build(root) 做三件事：dfs1 递归求 fa / dep，回溯时汇总 sz 并选出重儿子 son；dfs2 按“重儿子优先”分配 dfn 和链头 top；最后 seg_build 把 base 建成线段树。线段树的 range_add 用四分式骨架——先剪掉完全不相交的分支，再处理完全包含的分支，最后才递归两侧。

路径操作 path_add / path_sum 分两步。第一步，只要两点不在同一条重链（top[u] != top[v]），就比较两边链头的深度，让链头更深的那一侧结算 [dfn[top[u]], dfn[u]] 这一段，然后跳到链头的父节点。比的是链头而不是点本身：点本身更深不代表它那一侧该先结算，而链头更深说明这一侧整条链都在 LCA 以下，可以整段丢掉。第二步，循环退出时两点已在同一条重链上，把较浅的点当 $u$ （代码里是 if (dep[u] > dep[v]) swap(u, v)），再对 [dfn[u], dfn[v]] 做最后一次区间操作—— 这一段就是到 LCA 为止的收尾，漏了它路径就不闭合。子树操作 subtree_add / subtree_sum 不需要跳链，直接处理连续区间 [dfn[u], dfn[u] + sz[u] - 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
232
233
234
235
236
237
238
239
240/**
 * 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-10-29 16:05
 */
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// ===================== 重链剖分 + 懒标记线段树 =====================
// 骨架取自 rbook 模板 hld：全部是全局数组加普通函数，没有 struct/class。
// 模板把代码分成两段：sgt 段只管数组 base[1..n] 上的区间加/区间和，
// hld 段负责把树上路径与子树翻译成 base 上的连续区间。
// 使用顺序：直接读 n / mod -> 读点权到 a[] -> add_edge 加边 -> build(root) -> 操作。
// 节点编号、dfn 编号、线段树下标全部 1 起。

const int maxn = 100000 + 5; // 本题 n <= 1e5。模板要求 n <= maxn，不能越界

int n, mod; // n：节点数；mod：题目给的取模数 P，所有输出都对它取模

/*------------------------ sgt 代码 开始 ------------------------*/
// 懒标记线段树：维护数组 base[1..n]，支持区间加、区间和对 mod 取模。
ll base[maxn];        // base[t]：按 dfn 重排后的点权，线段树就建在它上面
ll tr[maxn << 2];     // tr[p]：节点 p 覆盖区间的和（已取模）
ll lazy[maxn << 2];   // lazy[p]：节点 p 上欠着、还没下发的“整段加”的值

// 把可能为负的 x 归一到 [0, mod)：只用在“外来值”上（输入的初值和增量）。
ll norm(ll x) { return (x % mod + mod) % mod; }

int ls(int p) { return p << 1; }     // p 的左儿子 2p
int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1

// 给节点 p 的整段区间加 value：区间和增加 value * 长度，懒标记也累加 value。
// 这样整段加可以在节点摘要上 O(1) 结算，不必下到叶子。
void apply(int p, int l, int r, ll value) {
    value = norm(value);
    tr[p] = (tr[p] + value * (r - l + 1)) % mod;
    lazy[p] = (lazy[p] + value) % mod;
}

void pushdown(int p, int l, int r) {
    // 懒标记为 0 无事可做；叶子没有儿子可下放，必须提前返回，
    // 否则 mid = l，会递归进入自己并且写越界的 tr[2p]。
    if (!lazy[p] || l == r) return;
    int mid = (l + r) >> 1;
    apply(ls(p), l, mid, lazy[p]);
    apply(rs(p), mid + 1, r, lazy[p]);
    lazy[p] = 0;
}

// 用 base[1..n] 建树。入口顺手清掉 lazy[p]：这样就不必整体清零 lazy 数组。
void seg_build(int p, int l, int r) {
    lazy[p] = 0;
    if (l == r) {
        tr[p] = norm(base[l]);
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(ls(p), l, mid);
    seg_build(rs(p), mid + 1, r);
    tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod;
}

// 区间加：把 [ql, qr] 整体加 value。
// 四分式：先剪掉完全不相交的分支，再处理完全包含的分支，最后才递归两侧。
void range_add(int ql, int qr, ll value, int p, int l, int r) {
    if (qr < l || r < ql) return; // 不相交，剪掉
    if (ql <= l && r <= qr) {     // 完全包含，整段打标记
        apply(p, l, r, value);
        return;
    }
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    range_add(ql, qr, value, ls(p), l, mid);
    range_add(ql, qr, value, rs(p), mid + 1, r);
    tr[p] = (tr[ls(p)] + tr[rs(p)]) % mod;
}

// 区间和：与 range_add 同一副骨架，只是“不相交”返回 0、“完全包含”返回摘要。
ll range_sum(int ql, int qr, int p, int l, int r) {
    if (qr < l || r < ql) return 0;      // 不相交
    if (ql <= l && r <= qr) return tr[p]; // 完全包含
    pushdown(p, l, r);
    int mid = (l + r) >> 1;
    ll answer = range_sum(ql, qr, ls(p), l, mid);
    answer += range_sum(ql, qr, rs(p), mid + 1, r);
    return answer % mod;
}
/*------------------------ sgt 代码 结束 ------------------------*/

/*------------------------ hld 代码 开始 ------------------------*/
// 树链剖分：g 存树，a 存原点权，6 个核心数组维护树上信息。
vector<int> g[maxn]; // g[u]：u 的邻接表（无向树，两边都存）
ll a[maxn];          // a[u]：原树上的点权

int fa[maxn];  // fa[u]：父亲，根的 fa 为 0
int dep[maxn]; // dep[u]：深度，根为 1
int sz[maxn];  // sz[u]：子树大小（含自己）
int son[maxn]; // son[u]：重儿子，叶子为 0
int top[maxn]; // top[u]：所在重链的链头
int dfn[maxn]; // dfn[u]：线段树上的位置（DFS 新编号）
int timer;     // dfn 计数器

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

// 第一遍 DFS：往下求 fa、dep，回溯时汇总 sz 并选出重儿子 son。
// 重儿子 = 子树最大的儿子；用 sz[son[u]] 比较，sz[0] 恒为 0 顺带处理了“还没有重儿子”。
void dfs1(int u, int father) {
    fa[u] = father;
    dep[u] = dep[father] + 1; // 根的 father 为 0、dep[0] 恒为 0，故根深度为 1
    sz[u] = 1;                // 先算上自己
    son[u] = 0;               // 叶子没有重儿子
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 第二遍 DFS：重儿子优先分配 dfn，保证整条重链的编号连续。
// 每个轻儿子自己开一条新链，所以传进去的链头就是它自己。
void dfs2(int u, int head) {
    top[u] = head;
    dfn[u] = ++timer;
    base[timer] = a[u]; // 把点权搬到 sgt 段的数组上，线段树维护的就是它
    if (son[u]) dfs2(son[u], head);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

// 预处理入口：加完边之后调用一次。其余数组在 dfs1 / dfs2 / seg_build 里逐点覆写，
// 所以不需要事先清零。sz[u] 必须在 dfs2 之前算好，因为子树区间
// [dfn[u], dfn[u] + sz[u] - 1] 依赖它。
void build(int root) {
    dfs1(root, 0);      // 填 fa / dep / sz / son
    timer = 0;          // 从 1 重新分配 dfn
    dfs2(root, root);   // 填 top / dfn / base
    seg_build(1, 1, n); // 交给 sgt 段
}

// 只跳链求 LCA，O(log n)。本题用不到，保留是因为它和路径操作同构。
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

// 路径 (u, v) 上所有点加 delta。
// 不在同一条重链时，处理“链头更深”那一侧的整段 [dfn[top[u]], dfn[u]]，
// 然后 u 跳到链头的父亲，即跨过一条轻边。每条轻边都让子树大小至少翻倍，
// 所以最多跳 O(log n) 次。两侧链头相同时，剩下的就是同一条链上的一段区间。
void path_add(int u, int v, ll delta) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        range_add(dfn[top[u]], dfn[u], delta, 1, 1, n);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    range_add(dfn[u], dfn[v], delta, 1, 1, n);
}

// 路径 (u, v) 上所有点的和。跳链过程与 path_add 完全一致。
ll path_sum(int u, int v) {
    ll answer = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        answer = (answer + range_sum(dfn[top[u]], dfn[u], 1, 1, n)) % mod;
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    answer = (answer + range_sum(dfn[u], dfn[v], 1, 1, n)) % mod;
    return answer;
}

// 子树操作不需要跳链：以 u 为根的子树在 dfn 上正好是连续区间
// [dfn[u], dfn[u] + sz[u] - 1]，一次区间操作即可。
void subtree_add(int u, ll delta) {
    range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n);
}

ll subtree_sum(int u) {
    return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n);
}
/*------------------------ hld 代码 结束 ------------------------*/

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

    int m, root;                  // 操作数、根
    cin >> n >> m >> root >> mod; // 点数和模数直接读进全局

    for (int u = 1; u <= n; ++u) g[u].clear(); // 清掉上一组留下的边

    for (int i = 1; i <= n; i++) cin >> a[i]; // 原编号下的点权，取模在 seg_build 里做

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

    build(root); // 两遍 DFS + 建线段树

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

    return 0;
}

预处理（两遍遍历 + 建树）： $O(n)$ 。
子树加 / 子树和： $O(\log n)$ 。
路径加 / 路径和： $O(\log^2 n)$ （ $O(\log n)$ 段，每段线段树 $O(\log n)$ ）。
空间： $O(n)$ 。
总时间： $O(n + m \log^2 n)$ ， $n, m \leqslant 10^5$ 时约 $10^5 \times 289$ 次基本操作。

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

dfs1(u, father)：往下递归求 fa 和 dep，回溯时汇总 sz、挑出重儿子 son。
dfs2(u, head)：先递归重儿子（沿用链头 head），再按邻接表顺序递归各轻儿子（各自开新链），于是整条重链的 dfn 连续。

两遍都是递归写法，递归深度等于树高。 $n \le 10^5$ 的链形树最深递归 $10^5$ 层，实测需要约 8 MiB 栈；判题器的栈上限默认与内存上限相同（远大于此），所以不会爆栈。

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]+sz[u]-1]
  重链 dfs 连续编号；路径拆成 O(log n) 条重链段（轻边让子树大小翻倍）
        |
        v
重链剖分 + 懒标记线段树（main.cpp）
  dfs1(u, father)：递归定 fa/dep，回溯汇总 sz 并选出重儿子 son
  dfs2(u, head)：重儿子优先分配 dfn，记录链头 top，再建线段树
  路径操作：while (top[u] != top[v]) 处理整段 [dfn[top[u]], dfn[u]] 后跳链
  子树操作：直接区间 [dfn[u], dfn[u]+sz[u]-1]
  线段树：区间加 / 区间和，lazy 整段结算
        |
        v
复杂度 O(n) 预处理 + O(log n)（子树）/ O(log^2 n)（路径）每次操作

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