树链剖分
代码模板树链剖分先让重儿子连续编号,把树上路径拆成 $O(\log n)$ 段数组区间,再交给线段树处理。
一句话算法
树链剖分先让重儿子连续编号,把树上路径拆成
问题模型
本文讨论重链剖分:树的边不变,根在预处理前确定。给定一棵
- 树上两点路径加;
- 树上两点路径求和;
- 某个子树整体加;
- 某个子树求和。
树上路径不是数组区间,不能直接套线段树。树链剖分的目标是把树上的路径拆成少量连续区间。
核心直觉
树剖只做一件核心的事:
DFS 编号时,永远优先走重儿子。
重儿子是子树节点数最多的儿子,不是编号最大或深度最大的儿子。并列时任选一个,叶子没有重儿子。连向重儿子的边叫重边,其余父子边叫轻边;由重边连接的极大路径叫重链,单独的点也可以是一条链。
普通 DFS 序已经能把子树变成区间,但任意路径仍可能零散。我们只改变访问儿子的顺序:先把重儿子一路走到底,再处理沿途留下的轻子树。这样一来,重链也连续了。
图中根为 1,sz[3]=3 > sz[2]=1,所以 son[1]=3;4、5 的子树同样大,这里选 4。三条重链是 1→3→4、5、2。下面始终使用这一种合法编号:
原节点 u |
1 | 3 | 4 | 5 | 2 |
|---|---|---|---|---|---|
dfn[u] |
1 | 2 | 3 | 4 | 5 |
top[u] |
1 | 1 | 1 | 5 | 2 |
注意,dfn 是位置,节点权值应写到 base[dfn[u]] = a[u],线段树维护的是这份重排后的数组。
树上重链:1 -> 3 -> 4
DFS 编号:1 2 3
路径查询时,如果两个点不在同一条重链,就把更深的链头到当前点这一段处理掉,然后跳到链头的父亲。每跳一次都跨过一条轻边,而轻边最多跨
关键数组
fa[u]:父亲;dep[u]:深度;sz[u]:子树大小;son[u]:重儿子;top[u]:当前重链的链头;dfn[u]:DFS 新编号;rev[dfn]:新编号对应的原节点。
子树也会变成连续区间:
算法步骤
第一次 DFS
- 计算
fa[u]、dep[u]。 - 统计
sz[u]。 - 找到子树最大的儿子,记为
son[u]。
第二次 DFS
- 从链头开始给节点分配
dfn。 - 优先递归重儿子,让重链编号连续。
- 再递归所有轻儿子,每个轻儿子开启一条新链。
从递归步骤到竞赛模板
常见递归写法是 dfs1 统计大小、dfs2 重儿子优先编号。两份模板都用全局数组(Python 用列表)和独立函数,并用循环完成相同的依赖关系:
- 生成父亲在儿子前面的
order,记录fa、dep。 - 倒着扫描
order,这时所有儿子的sz已知,可以计算父亲的sz、son。 - 用栈做真正的 DFS:先压轻儿子,再压重儿子。栈后进先出,所以重儿子最先访问;轻儿子令
top[v]=v,重儿子继承top[u]。
第一遍的 order 只用于统计大小,不能当作最终的 dfn。第二遍才负责生成重儿子优先的 DFS 序。链形树有
路径操作
处理路径 (u, v):
- 当
top[u] != top[v]:- 选择链头更深的一边;
- 在线段树上处理
[dfn[top[u]], dfn[u]]; - 令
u = fa[top[u]]。
- 最后两点在同一条重链上,交换端点使
dep[u] <= dep[v],再处理[dfn[u], dfn[v]]。
例如路径 2→1→3→4:top[2]=2 比 top[4]=1 更深,先处理 [5,5],令 u=fa[2]=1;此时与 4 同链,处理 [1,3]。虽然节点 4 本身更深,第一步仍应该跳 2 所在的链。判断的是链头深度。
路径 4→3→5 则拆成 [4,4] 和 [2,3]。两段互不重叠,最近公共祖先 3 只算一次。
子树操作
同一张图中,节点 3 的子树是 3、4、5,对应 [2,4]。因此子树修改、查询都只需要一次区间操作:
L = dfn[u]
R = dfn[u] + sz[u] - 1
树剖只是决定区间边界。区间加、区间和由懒标记线段树完成:给长度为 len 的区间加 delta,区间和增加 delta * len,懒标记增加 delta;访问部分区间前先下传标记。
算法证明
核心不变量:每条重链在 DFS 序上是连续区间。
- 第二次 DFS 总是先访问重儿子,所以从链头沿重儿子一直走的节点会被连续编号。
- 轻儿子会开启新链,离开当前重链后才递归,因此不会插入到当前重链的编号中间。
- 子树是普通 DFS 序的连续区间,优先重儿子不会破坏 DFS 序的子树连续性。
为什么跳链不会漏点或越过 LCA?
循环保持:未处理的部分恰好是当前 u 到 v 的简单路径。设 t=top[u] 是两个链头中较深的一个。若 LCA 在 t 下方,则 v 也在 t 的子树内;v 要么与 u 同链,要么其链头比 t 更深,都与当前选择矛盾。因此 [t,u] 完全属于待处理路径,可以整段取走。
取走后,从 fa[t] 继续,既不重复链头,也不会漏掉链头上方的点。每一步都缩短未处理路径;同链时浅端点就是 LCA,最后一次区间操作恰好处理剩余部分。因此所有片段不重不漏。
为什么路径只会拆成
设 v 是 u 的轻儿子,h 是重儿子。由于重儿子不小于轻儿子:
所以沿轻边向下,子树规模不到原来的一半;沿轻边向上,子树规模超过原来的两倍。即使多个儿子并列最大,这个不等式仍成立。
沿着轻边向上跳时,子树规模至少翻倍:
因此任意点到根最多跨
复杂度分析
预处理两次 DFS:
- 时间复杂度:
。 - 空间复杂度:
。
每次路径修改或路径查询:
- 拆成
段; - 每段在线段树上操作
; - 总时间复杂度:
。
子树修改和子树查询是一次线段树区间操作,时间复杂度
代码模板
两份模板提供相同接口,不使用 struct 或 class。数组下标和区间端点都从 1 开始,所有区间均为闭区间。
| 接口 | 用途 |
|---|---|
init(n, mod) |
清空邻接表;每组数据重新调用。其余数组由 build 逐点覆写,不需要手工清零 |
a[u]、add_edge(u,v) |
设置初值、添加无向边 |
build(root) |
固定根,预处理并建立线段树;每次初始化后调用一次 |
path_add(u,v,delta) / path_sum(u,v) |
路径加 / 路径和,包含两个端点 |
subtree_add(u,delta) / subtree_sum(u) |
子树加 / 子树和,包含 u |
lca(u,v) |
只跳链求 LCA, |
C++ 版使用定长全局数组,maxn 按题目约束调整,且必须满足 tr、lazy 占用 4 * maxn 个 long long,maxn 开到
要求输入是一棵连通树,root 在 1..n 内。模板处理取模后的和;初值和增量可以是负数,输出统一落在 [0,mod-1]。C++ 约定 long long 范围内,乘法使用 long long。不取模的问题需要同步修改线段树与路径累加处,并检查和及乘积的范围。
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 节点与区间均为 1 下标;init -> 填 a / 加边 -> build -> 操作。
// n >= 1,1 <= mod <= 2^31-1;所有权值、增量用 long long。
const int maxn = 100000 + 5; // 按题目规模调整,n 不能超过 maxn
int n, mod;
vector<int> g[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], dfn[maxn], rev[maxn];
ll a[maxn], base[maxn], tr[maxn << 2], lazy[maxn << 2];
ll norm(ll x) { return (x % mod + mod) % mod; }
// 多组数据只需要清邻接表:旧边必须走。
// 其余数组在 build() / seg_build() 里逐点重新赋值,旧值不会影响结果。
void init(int count, int modulus) {
n = count; mod = modulus;
for (int u = 1; u <= n; ++u) g[u].clear();
}
void add_edge(int u, int v) {
g[u].push_back(v); g[v].push_back(u);
}
void apply(int u, int l, int r, long long value) {
value = norm(value);
tr[u] = (tr[u] + value * (r - l + 1)) % mod;
lazy[u] = (lazy[u] + value) % mod;
}
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;
}
void seg_build(int u, int l, int r) {
lazy[u] = 0; // 建树时顺手清懒标记,init 就不必整体清零
if (l == r) {
tr[u] = norm(base[l]);
return;
}
int mid = (l + r) >> 1;
seg_build(u << 1, l, mid);
seg_build(u << 1 | 1, mid + 1, r);
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}
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);
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}
long long range_sum(int ql, int qr, int u, int l, int r) {
if (ql <= l && r <= qr) return tr[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,避免链形树的 O(n) 递归栈。
void build(int root) {
static int order[maxn], stk[maxn];
int cnt = 0;
order[cnt++] = root;
fa[root] = 0; dep[root] = 1; // 显式写根父亲,不依赖 fa 的预清零
for (int i = 0; i < cnt; ++i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1;
order[cnt++] = v;
}
}
for (int i = n - 1; i >= 0; --i) {
int u = order[i];
sz[u] = 1; son[u] = 0;
int best = 0, best_size = 0; // 局部变量比较,不依赖 son[] 的旧值
for (int v : g[u]) {
if (v == fa[u]) continue;
sz[u] += sz[v];
if (sz[v] > best_size) { best_size = sz[v]; best = v; }
}
son[u] = best;
}
int timer = 0, tp = 0;
stk[tp++] = root;
top[root] = root;
while (tp > 0) {
int u = stk[--tp];
dfn[u] = ++timer; rev[timer] = u; base[timer] = a[u];
// 轻儿子先入栈,重儿子后入栈,故重儿子先被访问。
for (int v : g[u]) {
if (v == fa[u] || v == son[u]) continue;
top[v] = v; stk[tp++] = v;
}
if (son[u]) {
top[son[u]] = top[u]; stk[tp++] = son[u];
}
}
seg_build(1, 1, 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;
}
void path_add(int u, int v, long long 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);
}
long long path_sum(int u, int v) {
long long answer = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n);
answer %= mod;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
answer += range_sum(dfn[u], dfn[v], 1, 1, n);
return answer % mod;
}
void subtree_add(int u, long long delta) {
range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n);
}
long long subtree_sum(int u) {
return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n);
}
兼容 Python 3.8+,无需提高递归上限。大数据仍需结合评测时限和内存限制选择语言。
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
# Python 3.8+;全局列表与函数。节点、区间均为 1 下标。
# init(n, mod) -> 填 a / add_edge -> build(root) -> 路径与子树操作。
# 一次维护一棵静态树;新数据必须重新 init。mod 为正整数。
def init(count, modulus):
global n, mod, g, fa, dep, sz, son, top, dfn, rev, a, base, tr, lazy
n, mod = count, modulus
g = [[] for _ in range(n + 1)]
N = n + 1
# 同长度的数组一行建完;生成器里每次都是新列表,不会互相共享。
# 不要写成 [[0] * N] * 9 —— 那样 9 个名字会指向同一个列表。
fa, dep, sz, son, top, dfn, rev, a, base = ([0] * N for _ in range(9))
tr, lazy = [0] * (4 * n + 5), [0] * (4 * n + 5)
def add_edge(u, v):
g[u].append(v)
g[v].append(u)
def apply(u, l, r, a):
a %= mod
# 区间长度是 r - l + 1;先取模再加,防止数值无限增长。
tr[u] = (tr[u] + a * (r - l + 1)) % mod
lazy[u] = (lazy[u] + a) % mod
def pushdown(u, l, r):
# 叶节点没有儿子可下传;lazy 为 0 时无事可做。
if lazy[u] == 0 or l == r:
return
mid = (l + r) >> 1 # 除以 2 向下取整
apply(u << 1, l, mid, lazy[u]) # 左儿子编号 2u
apply(u << 1 | 1, mid + 1, r, lazy[u]) # 右儿子编号 2u+1
lazy[u] = 0
def seg_build(u, l, r, base):
if l == r:
tr[u] = base[l] % mod
return
mid = (l + r) >> 1
seg_build(u << 1, l, mid, base)
seg_build(u << 1 | 1, mid + 1, r, base)
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod
def range_add(ql, qr, a, u, l, r):
if ql <= l and r <= qr:
apply(u, l, r, a)
return
pushdown(u, l, r)
mid = (l + r) >> 1
if ql <= mid:
range_add(ql, qr, a, u << 1, l, mid)
if qr > mid:
range_add(ql, qr, a, u << 1 | 1, mid + 1, r)
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod
def range_sum(ql, qr, u, l, r):
if ql <= l and r <= qr:
return tr[u]
pushdown(u, l, r)
mid = (l + r) >> 1
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
def build(root):
# 父亲在前,逆序时儿子的子树大小已经算好。
order = [root]
dep[root] = 1
for u in order:
for v in g[u]:
if v == fa[u]:
continue
fa[v] = u
dep[v] = dep[u] + 1
order.append(v)
for u in reversed(order):
sz[u] = 1
for v in g[u]:
if v == fa[u]:
continue
sz[u] += sz[v]
if sz[v] > sz[son[u]]:
son[u] = v
timer = 0
stack = [root]
top[root] = root
while stack:
u = stack.pop()
timer += 1
dfn[u] = timer
rev[timer] = u
base[timer] = a[u]
# 后进先出:先压轻儿子,再压重儿子,保持 DFS 的子树连续性。
for v in g[u]:
if v == fa[u] or v == son[u]:
continue
top[v] = v
stack.append(v)
if son[u]:
top[son[u]] = top[u]
stack.append(son[u])
seg_build(1, 1, n, base)
def lca(u, v):
while top[u] != top[v]:
if dep[top[u]] < dep[top[v]]:
u, v = v, u
u = fa[top[u]]
return u if dep[u] < dep[v] else v
def path_add(u, v, delta):
while top[u] != top[v]:
# 处理链头更深的一边,再跨过链头上方的轻边。
if dep[top[u]] < dep[top[v]]:
u, v = v, u
range_add(dfn[top[u]], dfn[u], delta, 1, 1, n)
u = fa[top[u]]
# 同一条链上:浅的是 LCA,区间就是 [dfn[u], dfn[v]]。
if dep[u] > dep[v]:
u, v = v, u
range_add(dfn[u], dfn[v], delta, 1, 1, n)
def path_sum(u, v):
answer = 0
while top[u] != top[v]:
if dep[top[u]] < dep[top[v]]:
u, v = v, u
answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n)
answer %= mod
u = fa[top[u]]
if dep[u] > dep[v]:
u, v = v, u
answer += range_sum(dfn[u], dfn[v], 1, 1, n)
return answer % mod
def subtree_add(u, delta):
range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n)
def subtree_sum(u):
return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n)
完整代码
输入格式:第一行 n m root mod,第二行给出 n 个初始点权,随后 n-1 行无向边,再给出 m 行操作:
1 x y z:路径x到y的点权加z。2 x y:输出路径和对mod取模的结果。3 x z:以固定根为准,子树x的点权加z。4 x:输出子树和对mod取模的结果。
以下程序包含模板和读入输出,可独立运行。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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 节点与区间均为 1 下标;init -> 填 a / 加边 -> build -> 操作。
// n >= 1,1 <= mod <= 2^31-1;所有权值、增量用 long long。
const int maxn = 100000 + 5; // 按题目规模调整,n 不能超过 maxn
int n, mod;
vector<int> g[maxn];
int fa[maxn], dep[maxn], sz[maxn], son[maxn], top[maxn], dfn[maxn], rev[maxn];
ll a[maxn], base[maxn], tr[maxn << 2], lazy[maxn << 2];
ll norm(ll x) { return (x % mod + mod) % mod; }
// 多组数据只需要清邻接表:旧边必须走。
// 其余数组在 build() / seg_build() 里逐点重新赋值,旧值不会影响结果。
void init(int count, int modulus) {
n = count; mod = modulus;
for (int u = 1; u <= n; ++u) g[u].clear();
}
void add_edge(int u, int v) {
g[u].push_back(v); g[v].push_back(u);
}
void apply(int u, int l, int r, long long value) {
value = norm(value);
tr[u] = (tr[u] + value * (r - l + 1)) % mod;
lazy[u] = (lazy[u] + value) % mod;
}
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;
}
void seg_build(int u, int l, int r) {
lazy[u] = 0; // 建树时顺手清懒标记,init 就不必整体清零
if (l == r) {
tr[u] = norm(base[l]);
return;
}
int mid = (l + r) >> 1;
seg_build(u << 1, l, mid);
seg_build(u << 1 | 1, mid + 1, r);
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}
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);
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod;
}
long long range_sum(int ql, int qr, int u, int l, int r) {
if (ql <= l && r <= qr) return tr[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,避免链形树的 O(n) 递归栈。
void build(int root) {
static int order[maxn], stk[maxn];
int cnt = 0;
order[cnt++] = root;
fa[root] = 0; dep[root] = 1; // 显式写根父亲,不依赖 fa 的预清零
for (int i = 0; i < cnt; ++i) {
int u = order[i];
for (int v : g[u]) {
if (v == fa[u]) continue;
fa[v] = u; dep[v] = dep[u] + 1;
order[cnt++] = v;
}
}
for (int i = n - 1; i >= 0; --i) {
int u = order[i];
sz[u] = 1; son[u] = 0;
int best = 0, best_size = 0; // 局部变量比较,不依赖 son[] 的旧值
for (int v : g[u]) {
if (v == fa[u]) continue;
sz[u] += sz[v];
if (sz[v] > best_size) { best_size = sz[v]; best = v; }
}
son[u] = best;
}
int timer = 0, tp = 0;
stk[tp++] = root;
top[root] = root;
while (tp > 0) {
int u = stk[--tp];
dfn[u] = ++timer; rev[timer] = u; base[timer] = a[u];
// 轻儿子先入栈,重儿子后入栈,故重儿子先被访问。
for (int v : g[u]) {
if (v == fa[u] || v == son[u]) continue;
top[v] = v; stk[tp++] = v;
}
if (son[u]) {
top[son[u]] = top[u]; stk[tp++] = son[u];
}
}
seg_build(1, 1, 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;
}
void path_add(int u, int v, long long 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);
}
long long path_sum(int u, int v) {
long long answer = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n);
answer %= mod;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
answer += range_sum(dfn[u], dfn[v], 1, 1, n);
return answer % mod;
}
void subtree_add(int u, long long delta) {
range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n);
}
long long subtree_sum(int u) {
return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count, m, root, modulus;
cin >> count >> m >> root >> modulus;
init(count, modulus);
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = norm(a[i]);
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
build(root);
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
long long 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;
long long z;
cin >> x >> z;
subtree_add(x, z);
} else {
int x;
cin >> x;
cout << subtree_sum(x) << '\n';
}
}
return 0;
}
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
# Python 3.8+;全局列表与函数。节点、区间均为 1 下标。
# init(n, mod) -> 填 a / add_edge -> build(root) -> 路径与子树操作。
# 一次维护一棵静态树;新数据必须重新 init。mod 为正整数。
def init(count, modulus):
global n, mod, g, fa, dep, sz, son, top, dfn, rev, a, base, tr, lazy
n, mod = count, modulus
g = [[] for _ in range(n + 1)]
N = n + 1
# 同长度的数组一行建完;生成器里每次都是新列表,不会互相共享。
# 不要写成 [[0] * N] * 9 —— 那样 9 个名字会指向同一个列表。
fa, dep, sz, son, top, dfn, rev, a, base = ([0] * N for _ in range(9))
tr, lazy = [0] * (4 * n + 5), [0] * (4 * n + 5)
def add_edge(u, v):
g[u].append(v)
g[v].append(u)
def apply(u, l, r, a):
a %= mod
# 区间长度是 r - l + 1;先取模再加,防止数值无限增长。
tr[u] = (tr[u] + a * (r - l + 1)) % mod
lazy[u] = (lazy[u] + a) % mod
def pushdown(u, l, r):
# 叶节点没有儿子可下传;lazy 为 0 时无事可做。
if lazy[u] == 0 or l == r:
return
mid = (l + r) >> 1 # 除以 2 向下取整
apply(u << 1, l, mid, lazy[u]) # 左儿子编号 2u
apply(u << 1 | 1, mid + 1, r, lazy[u]) # 右儿子编号 2u+1
lazy[u] = 0
def seg_build(u, l, r, base):
if l == r:
tr[u] = base[l] % mod
return
mid = (l + r) >> 1
seg_build(u << 1, l, mid, base)
seg_build(u << 1 | 1, mid + 1, r, base)
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod
def range_add(ql, qr, a, u, l, r):
if ql <= l and r <= qr:
apply(u, l, r, a)
return
pushdown(u, l, r)
mid = (l + r) >> 1
if ql <= mid:
range_add(ql, qr, a, u << 1, l, mid)
if qr > mid:
range_add(ql, qr, a, u << 1 | 1, mid + 1, r)
tr[u] = (tr[u << 1] + tr[u << 1 | 1]) % mod
def range_sum(ql, qr, u, l, r):
if ql <= l and r <= qr:
return tr[u]
pushdown(u, l, r)
mid = (l + r) >> 1
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
def build(root):
# 父亲在前,逆序时儿子的子树大小已经算好。
order = [root]
dep[root] = 1
for u in order:
for v in g[u]:
if v == fa[u]:
continue
fa[v] = u
dep[v] = dep[u] + 1
order.append(v)
for u in reversed(order):
sz[u] = 1
for v in g[u]:
if v == fa[u]:
continue
sz[u] += sz[v]
if sz[v] > sz[son[u]]:
son[u] = v
timer = 0
stack = [root]
top[root] = root
while stack:
u = stack.pop()
timer += 1
dfn[u] = timer
rev[timer] = u
base[timer] = a[u]
# 后进先出:先压轻儿子,再压重儿子,保持 DFS 的子树连续性。
for v in g[u]:
if v == fa[u] or v == son[u]:
continue
top[v] = v
stack.append(v)
if son[u]:
top[son[u]] = top[u]
stack.append(son[u])
seg_build(1, 1, n, base)
def lca(u, v):
while top[u] != top[v]:
if dep[top[u]] < dep[top[v]]:
u, v = v, u
u = fa[top[u]]
return u if dep[u] < dep[v] else v
def path_add(u, v, delta):
while top[u] != top[v]:
# 处理链头更深的一边,再跨过链头上方的轻边。
if dep[top[u]] < dep[top[v]]:
u, v = v, u
range_add(dfn[top[u]], dfn[u], delta, 1, 1, n)
u = fa[top[u]]
# 同一条链上:浅的是 LCA,区间就是 [dfn[u], dfn[v]]。
if dep[u] > dep[v]:
u, v = v, u
range_add(dfn[u], dfn[v], delta, 1, 1, n)
def path_sum(u, v):
answer = 0
while top[u] != top[v]:
if dep[top[u]] < dep[top[v]]:
u, v = v, u
answer += range_sum(dfn[top[u]], dfn[u], 1, 1, n)
answer %= mod
u = fa[top[u]]
if dep[u] > dep[v]:
u, v = v, u
answer += range_sum(dfn[u], dfn[v], 1, 1, n)
return answer % mod
def subtree_add(u, delta):
range_add(dfn[u], dfn[u] + sz[u] - 1, delta, 1, 1, n)
def subtree_sum(u):
return range_sum(dfn[u], dfn[u] + sz[u] - 1, 1, 1, n)
def main():
import sys
# 按行读取,避免一次 split 整份输入产生大量临时对象。
read = sys.stdin.buffer.readline
count, m, root, modulus = map(int, read().split())
init(count, modulus)
a[1:] = list(map(int, read().split()))
for _ in range(n - 1):
u, v = map(int, read().split())
add_edge(u, v)
build(root)
out = []
for _ in range(m):
op, *args = map(int, read().split())
if op == 1:
path_add(*args)
elif op == 2:
out.append(str(path_sum(*args)))
elif op == 3:
subtree_add(*args)
else:
out.append(str(subtree_sum(*args)))
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
main()
测试用例
输入:
5 5 1 100
1 2 3 4 5
1 2
1 3
3 4
3 5
2 4 5
1 2 4 1
2 4 5
3 3 2
4 3
输出:
12
14
20
解释:
- 初始路径
4 -> 3 -> 5的和为4 + 3 + 5 = 12; - 路径
2 -> 4加1后,点1,2,3,4都增加; - 子树
3加2后,点3,4,5都增加,子树和变为20。
单点与负增量
1 5 1 7
3
2 1 1
1 1 1 -5
4 1
3 1 9
2 1 1
输出为 3、5、0(各占一行)。u=v 时点权查询仍包含这个点;mod=1 时所有输出都应为 0。
边权、方向与易错点
边权转点权。 把边 (fa[x],x) 的权值存到较深的端点 x,根的位置放 0。跳链阶段仍处理 [dfn[top[u]],dfn[u]],因为链头保存的正是本次跨过的轻边权。最后同链时,设 u 较浅,只处理 [dfn[u]+1,dfn[v]],排除 LCA 保存的那条路径外的边。空区间直接跳过;u=v 的边权和为 0。查询子树内部的边也要排除子树根位置。本文代码默认点权,切换模型时需修改这些边界。
非交换信息。 和、最大值不在意片段顺序;字符串、矩阵乘法、颜色段却在意路径方向。此时要分别累计原起点侧和终点侧,在线段树里维护区间正向与反向信息,再按路径顺序合并,不能直接照搬 path_sum 的累加方式。
常见错误。 比较 dep[top[u]],不是 dep[u];跳到 fa[top[u]],不是 fa[u] 或 top[u];在线段树上使用 dfn,不是原编号。不要把“在同一条重链”写成“两点深度相同”。
仅有子树操作时,普通 DFS 序就足够;只有 LCA 查询时,可以只保留树剖数组与 lca,不需要线段树。树剖预处理依赖固定边结构,直接增删边会使编号失效。
应用分类详解
树链剖分的本质是把树上路径转成少量数组区间。只要题目要求频繁操作树上路径,就应该考虑树剖。
一、路径修改和路径查询
典型模式: 两点之间路径加、路径求和、路径最大值。
识别信号: 出现“
核心建模: 用树剖拆路径,用线段树维护区间信息。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 树剖模板 | luogu-P3384 | 路径和 + 子树和 |
| 树上路径最大值 | luogu-P2590 | 线段树维护最大值 |
二、子树整体操作
典型模式: 修改某个点的整棵子树,或查询子树权值和。
识别信号: 出现“以
核心建模: 子树在 DFS 序中是连续区间 [dfn[u], dfn[u]+size[u]-1]。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 子树加与子树求和 | luogu-P3384 | DFS 序区间操作 |
| 树上统计 | 子树贡献类题目 | 把子树压成数组区间 |
三、路径拆分后的复合维护
典型模式: 线段树节点维护的不只是和,还可能是最大值、最小值、颜色段、矩阵等。
识别信号: 路径信息能通过区间合并得到。
核心建模: 树剖只负责拆路径;真正维护什么信息由线段树决定。
经典例题
1. luogu-P3384
树链剖分模板题,完整覆盖路径加、路径和、子树加、子树和。
2. luogu-P2590
练习单点赋值、路径求和与路径最大值:线段树同时维护和与最大值。最大值不取模,查询单位元应设为负无穷,避免全负权时错误返回 0。
3. luogu-P4114
路径最大边权类问题。适合练习边权转点权,以及路径查询时如何排除 LCA 点。