前置芝士：线段树，或树状数组，越熟练越好。
（当然这不是意味着你不会线段树就看不懂这篇博客。）
1. 何为树链剖分
树链剖分，简而言之，就是将树分成一条条链，然后用数据结构去维护这些链，以支持树上两点间的各种询问操作。
据我所知，树链剖分大约有三种，分别是重链剖分、长链剖分和实链剖分。其中的重链剖分最为常见，所以一般说树链剖分（简称树剖）就是指重链剖分。
注：重链剖分和长链剖分只能在有根树上用。
2. 重链剖分
-
预处理
这是普通 oi 题中的一颗树。这里我们钦定 1 为根。
在重链剖分中，有如下几个定义：
重儿子：树上每个节点的儿子中子树大小最大的称为重儿子。图中用红圈标出。
轻儿子：不是重儿子的点是轻儿子。
重边：连接每个重儿子及其父节点的边称为重边。图中用蓝色标出。
轻边：不是重边的边是轻边。
重链：以轻儿子为起点，只经过重边与重儿子的极长链。如图中 1 - 2 - 4 - 5，10 - 8 - 11 等。特别地，单独一个轻叶子节点也可以算一条重链。
轻链：重链以外，都是轻链。
这样，我们就可以发现树上每个节点都恰好只被一条重链包含。
那接下来要考虑的问题自然就变成了如何求重链。由重链的定义可知，我们可以进行一次 dfs，先求出每个节点的重儿子，然后让重儿子继承当前节点所在的重链，再以所有轻儿子为起点各再往下拉一条重链。这样，我们就求出了树中每一条重链。
重链求完之后，就需要维护。由于要用数据结构来维护重链，所以应该尽量让重链上所有点的编号连续。显然原树上重链的编号是不一定连续的，所以需要给树上每一个节点重新编号。为了使编号连续，我们采用 dfs 序的方式来重编号。在递归每个节点时，先给该节点编上号，随后优先递归其重儿子，这样就能够保证同一条重链上的编号连续。
上代码：
int dfn[100005]; // dfs 序
int sz[100005]; // 子树大小
int dep[100005]; // 深度
int top[100005]; // 所在重链链顶
int son[100005]; // 重儿子
int f[100005]; // 父亲
void dfs1(int x, int fa, int d) {
sz[x] = 1;
f[x] = fa;
dep[x] = d;
for (int i = head[x]; i != 0; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs1(v, x, d + 1);
sz[x] += sz[v];
if (sz[v] > sz[son[x]]) // son[x] 代表 x 的重儿子
son[x] = v;
}
}
}
void dfs2(int x, int t) { // t 表示当前重链的最上面的节点
dfn[x] = ++ncnt; // dfs 序
wt[ncnt] = w[x];
top[x] = t;
if (!son[x])
return;
dfs2(son[x], t); // 让重儿子继承当前重链并优先递归，确保编号连续
for (int i = head[x]; i != 0; i = nxt[i]) {
int v = to[i];
if (v != son[x] && v != f[x])
dfs2(v, v); // 以每个轻儿子为起点拉一条链
}
}
这是普通 oi 题中一颗被重新编号过的树。
可以看出，现在所有重链上的节点编号都连续了，可以用数据结构维护了。
2. 在线询问
对于一次询问的两个端点 \(u\) 和 \(v\)，我们用跳链的方法将原本不在同一条重链上的两个点放到同一条重链上。每次让所在链顶深度较深的点往上跳，跳到其链顶节点的父亲，一边跳一边在数据结构中统计区间 [dfn[top[x]], dfn[x]] 的答案。当两点跳到同一条链上后，再最后统计一遍浅的节点到深的节点这一段区间的答案就好了。
这里以区间和为例。
int Query_path(int u, int v) {
int ret = 0;
while (top[u] != top[v]) { // 当两点不在同一条链上
if (dep[top[u]] < dep[top[v]]) // 保证是链顶深度深的点在往上跳
swap(u, v);
ret += Query_sum(1, 1, N, dfn[top[u]], dfn[u]); // 统计被跳过区间的答案
ret %= p;
u = f[top[u]]; // 跳链
}
if (dep[u] > dep[v]) // 当两点在同一条链上时
swap(u, v);
ret += Query_sum(1, 1, N, dfn[u], dfn[v]); // 统计深度浅的节点到深的节点这段区间的答案
return ret % p;
}
在线修改同理。
void Add_path(int u, int v, int z) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
Add(1, 1, N, dfn[top[u]], dfn[u], z); // 修改整条链上的答案
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
Add(1, 1, N, dfn[u], dfn[v], z); // 最后再修改一次
}
现在，你已经会写树链剖分了。来打一个板子吧！
AC 代码：
#include <iostream>
#define int long long
using namespace std;
const int N = 262144;
int n, m, r, p;
int head[200005], nxt[200005], to[200005], cnt;
void add(int u, int v) { to[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt; }
int dfn[100005], sz[100005], dep[100005], top[100005], son[100005], f[100005];
int wt[N * 4], w[N * 4];
int ncnt;
void dfs1(int x, int fa, int d) {
sz[x] = 1;
f[x] = fa;
dep[x] = d;
for (int i = head[x]; i != 0; i = nxt[i]) {
int v = to[i];
if (v != fa) {
dfs1(v, x, d + 1);
sz[x] += sz[v];
if (sz[v] > sz[son[x]])
son[x] = v;
}
}
}
void dfs2(int x, int t) {
dfn[x] = ++ncnt;
wt[ncnt] = w[x];
top[x] = t;
if (!son[x])
return;
dfs2(son[x], t);
for (int i = head[x]; i != 0; i = nxt[i]) {
int v = to[i];
if (v != son[x] && v != f[x])
dfs2(v, v);
}
}
int sm[N * 4], tag[N * 4];
void pushdown(int o, int l, int r) {
if (tag[o] == 0)
return;
int t = tag[o];
int mid = l + r >> 1;
tag[o << 1] += t;
tag[o << 1 | 1] += t;
sm[o << 1] += (mid - l + 1) * t;
sm[o << 1 | 1] += (r - mid) * t;
tag[o] = 0;
}
void Build(int o, int l, int r) {
if (l == r) {
sm[o] = wt[l];
return;
}
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
sm[o] = sm[o << 1] + sm[o << 1 | 1];
}
void Add(int o, int l, int r, int L, int R, int k) {
if (L <= l && r <= R) {
sm[o] += (r - l + 1) * k;
tag[o] += k;
return;
}
pushdown(o, l, r);
int mid = l + r >> 1;
if (L <= mid)
Add(o << 1, l, mid, L, R, k);
if (R > mid)
Add(o << 1 | 1, mid + 1, r, L, R, k);
sm[o] = sm[o << 1] + sm[o << 1 | 1];
}
int Qsum(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return sm[o];
pushdown(o, l, r);
int mid = l + r >> 1, ret = 0;
if (L <= mid)
ret += Qsum(o << 1, l, mid, L, R);
if (R > mid)
ret += Qsum(o << 1 | 1, mid + 1, r, L, R);
return ret;
}
void Add_path(int u, int v, int z) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
Add(1, 1, N, dfn[top[u]], dfn[u], z);
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
Add(1, 1, N, dfn[u], dfn[v], z);
}
int Query_path(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ret += Qsum(1, 1, N, dfn[top[u]], dfn[u]);
ret %= p;
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
ret += Qsum(1, 1, N, dfn[u], dfn[v]);
return ret % p;
}
void Add_sbt(int x, int y) { Add(1, 1, N, dfn[x], dfn[x] + sz[x] - 1, y % p); }
int Query_sbt(int x) { return Qsum(1, 1, N, dfn[x], dfn[x] + sz[x] - 1) % p; }
signed main() {
cin >> n >> m >> r >> p;
for (int i = 1; i <= n; i++) scanf("%lld", w + i);
for (int i = 1, u, v; i <= n - 1; i++) {
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs1(r, 0, 1);
dfs2(r, r);
Build(1, 1, N);
for (int i = 1, op, x, y, z; i <= m; i++) {
cin >> op >> x;
if (op == 1) {
cin >> y >> z;
Add_path(x, y, z);
} else if (op == 2) {
cin >> y;
cout << Query_path(x, y) << "\n";
} else if (op == 3) {
cin >> y;
Add_sbt(x, y);
} else {
cout << Query_sbt(x) << "\n";
}
}
return 0;
}
树剖平均码量 100 多行，所以看到这么长的代码不要害怕。你会习惯的。
最后，来点小练习题：
最后
虽然树剖代码长，但是很好打。如果认真打的话这些板子一遍过没有问题。实在不行可以照着我代码打（不要脸.jpg
最后的最后，一定要多练！！！多练习才能真正学会新东西。
标签：剖分,int,top,dep,dfn,重链 From： https://www.cnblogs.com/forgotmyhandle/p/17822724.html