树链剖分

树链剖分先让重儿子连续编号，把树上路径拆成 $O(\log n)$ 段数组区间，再交给线段树处理。

  • 树
  • 树链剖分
  • 线段树

一句话算法

树链剖分先让重儿子连续编号，把树上路径拆成 O(log⁡n)O(\log n) 段数组区间，再交给线段树处理。

问题模型

给定一棵有根树，每个点有权值，要求支持：

  • 树上两点路径加；
  • 树上两点路径求和；
  • 某个子树整体加；
  • 某个子树求和。

树上路径不是数组区间，不能直接套线段树。树链剖分的目标是把树上的路径拆成少量连续区间。

核心直觉

树剖只做一件核心的事：

DFS 编号时，永远优先走重儿子。

重儿子是子树最大的儿子。这样一来，一条不断走重儿子的链，会在 DFS 序里变成连续区间。

树上重链： 1 -> 3 -> 6 -> 9
DFS 编号：dfn[1], dfn[1]+1, dfn[1]+2, dfn[1]+3

路径查询时，如果两个点不在同一条重链，就把更深的链头到当前点这一段处理掉，然后跳到链头的父亲。每跳一次都跨过一条轻边，而轻边最多跨 O(log⁡n)O(\log n) 次。

关键数组

  • parent[u]：父亲；
  • depth[u]：深度；
  • subtree_size[u]：子树大小；
  • heavy_son[u]：重儿子；
  • top[u]：当前重链的链头；
  • dfn[u]：DFS 新编号；
  • node_at[dfn]：新编号对应的原节点。

子树也会变成连续区间：

u 的子树⟺[dfn[u], dfn[u]+subtree_size[u]−1] u\text{ 的子树} \Longleftrightarrow [dfn[u],\ dfn[u]+subtree\_size[u]-1]

算法步骤

第一次 DFS

  1. 计算 parent[u]、depth[u]。
  2. 统计 subtree_size[u]。
  3. 找到子树最大的儿子，记为 heavy_son[u]。

第二次 DFS

  1. 从链头开始给节点分配 dfn。
  2. 优先递归重儿子，让重链编号连续。
  3. 再递归所有轻儿子，每个轻儿子开启一条新链。

路径操作

处理路径 (u, v)：

  1. 当 top[u] != top[v]：
    • 选择链头更深的一边；
    • 在线段树上处理 [dfn[top[u]], dfn[u]]；
    • 令 u = parent[top[u]]。
  2. 最后两点在同一条重链上，处理 [dfn[u], dfn[v]]。

算法证明

核心不变量：每条重链在 DFS 序上是连续区间。

  1. 第二次 DFS 总是先访问重儿子，所以从链头沿重儿子一直走的节点会被连续编号。
  2. 轻儿子会开启新链，离开当前重链后才递归，因此不会插入到当前重链的编号中间。
  3. 子树是普通 DFS 序的连续区间，优先重儿子不会破坏 DFS 序的子树连续性。

为什么路径只会拆成 O(log⁡n)O(\log n) 段？

若从节点经过轻边跳到父亲所在链，说明刚离开的子树不是父亲的最大子树，所以它的大小至多是父亲子树的一半。

沿着轻边向上跳时，子树规模至少翻倍：

1, 2, 4, 8, ⋯ , n 1,\ 2,\ 4,\ 8,\ \cdots,\ n

因此轻边数量最多是 O(log⁡n)O(\log n)。每跨一条轻边处理一段重链，所以路径被拆成 O(log⁡n)O(\log n) 段。

复杂度分析

预处理两次 DFS：

  • 时间复杂度：O(n)O(n)。
  • 空间复杂度：O(n)O(n)。

每次路径修改或路径查询：

  • 拆成 O(log⁡n)O(\log n) 段；
  • 每段在线段树上操作 O(log⁡n)O(\log n)；
  • 总时间复杂度：O(log⁡2n)O(\log^2 n)。

子树修改和子树查询是一次线段树区间操作，时间复杂度 O(log⁡n)O(\log n)。

代码实现

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

        #include <bits/stdc++.h>
using namespace std;

struct SegmentTree {
    vector<long long> sum;
    vector<long long> lazy;
    int mod = 1;

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

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

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

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

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

struct HeavyLightDecomposition {
    int n;
    int root;
    int mod;
    int timer = 0;
    vector<vector<int>> graph;
    vector<int> parent, depth, subtree_size, heavy_son;
    vector<int> top, dfn, node_at;
    vector<long long> value, ordered_value;
    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);
    }

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

    void dfs_decompose(int u, int chain_top) {
        top[u] = chain_top;
        dfn[u] = ++timer;
        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);
    }

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

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

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

测试用例

输入：

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。

应用分类详解

树链剖分的本质是把树上路径转成少量数组区间。只要题目要求频繁操作树上路径，就应该考虑树剖。

一、路径修改和路径查询

典型模式： 两点之间路径加、路径求和、路径最大值。

识别信号： 出现“uu 到 vv 的路径上所有点/边”并且操作次数很多。

核心建模： 用树剖拆路径，用线段树维护区间信息。

应用场景 经典题目 核心思路
树剖模板 luogu-P3384 路径和 + 子树和
树上路径最大值 luogu-P2590 线段树维护最大值

二、子树整体操作

典型模式： 修改某个点的整棵子树，或查询子树权值和。

识别信号： 出现“以 uu 为根的子树”。

核心建模： 子树在 DFS 序中是连续区间 [dfn[u], dfn[u]+size[u]-1]。

应用场景 经典题目 核心思路
子树加与子树求和 luogu-P3384 DFS 序区间操作
树上统计 子树贡献类题目 把子树压成数组区间

三、路径拆分后的复合维护

典型模式： 线段树节点维护的不只是和，还可能是最大值、最小值、颜色段、矩阵等。

识别信号： 路径信息能通过区间合并得到。

核心建模： 树剖只负责拆路径；真正维护什么信息由线段树决定。

经典例题

1. luogu-P3384

树链剖分模板题，完整覆盖路径加、路径和、子树加、子树和。

2. luogu-P2590

树上路径最大值。把线段树维护内容从区间和换成区间最大值即可。

3. luogu-P4114

路径最大边权类问题。适合练习边权转点权，以及路径查询时如何排除 LCA 点。

参考

  • 本目录草稿：book/pages/tree-algo/hld/灵魂.md
  • 本书相关章节：DFS 序