引言
尽管有些题会卡重链剖分，但它仍是一种强大的树上问题处理工具。
在许多资料中，『树链剖分』默认指重链剖分，因为它用得最多。本文明确区分『重链剖分』和『树链剖分』。
重链剖分
定义
本文中『树』默认为有根树。节点的『DFN 序』默认在 DFS 时优先遍历重边。
『重子节点』或『重儿子』是一个点所有子结点中，以它为根的子树最大的那个。
『重边』是从某个点连向其重儿子的边。
『重链』是由若干重边相连而成的链。不在任何重链上的点可以被视为包含 \(0\) 条边的重链。
实现
首先用一个 DFS 得到每个点的父亲、深度、子树大小和重儿子。
void dfs1(int u) {hson[u] = -1;siz[u] = 1;for (int j = 0; j < g[u].size(); j++) {int v = g[u][j];if (!dep[v]) {dep[v] = dep[u] + 1;fa[v] = u;dfs1(v);siz[u] += siz[v];if (hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;}}
}
接着再一个 DFS 得到每个点的所在重链顶、DFN 序，以及每个 DFN 序对应的点编号。
void dfs2(int u, int t) {top[u] = t;dfn[u] = ++cnt;if (hson[u] != -1) {dfs2(hson[u], t);for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (v != fa[u] && v != hson[u]) dfs2(v, v);}}
}
应用
维护路径信息
从两个点出发，不断跳链顶。由于同一条链上的 DFN 序是连续的，可以方便地套用维护序列的数据结构，如线段树。
下面以修改路径上节点权值、查询路径上的节点权值和为例。
void padd(int x, int y, int z) {while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);update(1, 1, n, dfn[top[x]], dfn[x], z);x = fa[top[x]];}if (dep[x] > dep[y]) swap(x, y);update(1, 1, n, dfn[x], dfn[y], z);
}
int psum(int x, int y) {int res = 0;while (top[x] != top[y]) {if (dep[top[x]] < dep[top[y]]) swap(x, y);res += query(1, 1, n, dfn[top[x]], dfn[x]);x = fa[top[x]];}if (dep[x] > dep[y]) swap(x, y);return res + query(1, 1, n, dfn[x], dfn[y]);
}
维护子树信息
同一个子树内的 DFN 序显然也是连续的。也可以套用维护序列的数据结构。
下面以修改子树内节点权值、查询子树内节点权值和为例。
void tadd(int x, int z) {update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, z % p);
}
int tsum(int x) {return query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) % p;
}
维护路径、子树信息时换根
对于路径信息，根节点是谁没有影响。
对于子树信息，当然不能在换根后重新 DFS。考虑将新树信息映射到原树上。例如，使用差分思想，将新树的子树表示成原树某两棵子树的差。具体问题具体分析。
查询两点最近公共祖先
类似倍增，两点不断跳链顶，直到跳到同一条重链上。LCA 就是深度更小的那个点。
int lca(int u, int v) {while (top[u] != top[v]) {if (dep[top[u]] > dep[top[v]])u = fa[top[u]];elsev = fa[top[v]];}return dep[u] > dep[v] ? v : u;
}