树链剖分
树链剖分
重链剖分
树链剖分：将树分割成若干条链的形式，用于维护树上的信息。
形式：
- 重链剖分
- 长链剖分
- 实链剖分
- 等等
重链剖分由于将树上数据的维护变成了序列数据的维护，因此可以用线段树等维护序列的数据结构便捷地维护。
定义申明
- 重儿子（Heavy Son）：对于一个节点
u，其所有子节点中子树大小最大的那个子节点称为重儿子。如果有多个最大，任意选一个。 - 轻儿子（Light Son）：除了重儿子以外的其他子节点。
- 重边（Heavy Edge）：连接节点
u和其重儿子的边。 - 轻边（Light Edge）：连接节点
u和其轻儿子的边。 - 重链（Heavy Chain）：由一系列重边连接而成的路径。重链的开头是轻儿子或根节点。
需要为每个节点 u 存储的信息：
father[u]：节点u的父节点。deep[u]：节点u的深度（根节点深度为0或1）。sz[u]：以u为根的子树的节点数量。son[u]：节点u的重儿子。top[u]：节点u所在重链的顶端节点。tid[u]（或id[u]）：节点u在 DFS 序（新编号） 中的位置。wt[dfn[u]]：DFS 序对应位置的节点权值。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。如图：
注意：
节点编号有：
- 原编号（节点ID）
- 范围：1 到 n
- 用途：
x,fa,edge[i].to等都使用这个编号体系 - 示例：根节点是1，它的子节点可能是2,3,4等
- DFS序编号 (
tid)- 范围：1 到 n
- 用途：线段树中的位置编号
- 映射：
tid[x]表示原节点x的DFS序位置
- 边的索引 (
edge下标)- 范围：1 到 cnt（边的计数器）
- 用途：邻接表中遍历边时使用
实现
共用两个DFS：
-
信息收集
目的： 计算每个节点的基础信息，为后续剖分做准备。
获得了以下基础信息：
- 每棵树的子树大小
- 标记父节点和深度
- 确定重儿子
具体步骤：
void dfs1(int x, int fa, int depth) // 节点id，fa id，节点在树上的深度； { sz[x] = 1; // 初始化节点子树大小 father[x] = fa; deep[x] = depth; // 节点在树上的深度 // 遍历该节点的所有子节点(链式前向星) for (int i = head[x]; i; i = edge[i].next) // i是指针 { Node v = edge[i].to; if (v == fa) continue; // 非有向边 dfs1(v, x, depth+1); sz[x] += sz[v]; // 判断重儿子 <- 没有重儿子/新节点更重 if (!son[x] or sz[v] > deep[son[x]]) son[x] = v; } } -
划分重链并生成DFS序
核心逻辑:
- DFS序分配 (
tid[])- 每个节点被访问时获得一个唯一的DFS序编号
- 关键技巧：先递归重儿子，保证同一条重链上的节点编号连续
- 重链划分 (
top[])tp参数表示当前重链的顶端节点- 重儿子继承父亲的链顶 (
dfs2(son[x], tp)) - 轻儿子自己成为新链的顶端 (
dfs2(轻儿子, 轻儿子))
具体步骤：
void dfs2(int x, int tp) { tid[x] = ++tidnum; pos[tid[x]] = x; // 反向映射，用于通过DFS序来查找节点 top[x] = tp; // 标记链顶 // 叶子节点特判 if (!son[x]) return; dfs2(son[x], tp); // 先对重儿子进行DFS保证DFS序的顺序 // 对轻节点进行遍历： // - 遍历所有节点 // - 判断是否是重节点： // ├── 不是：DFS并以它本身作为链顶 // └── 是：跳过 for (int i = head[x]; i; i = edge[x].next) { int v = edge[i].to; if (v != son[x] and v != father[x]) // 注意：无向边需特判父节点 { dfs2(v, v); } } } - DFS序分配 (
附：链式前行星代码
// 链式前向星
struct Node {
int to, next;
// int w; //权重
} edge[maxn << 2]; // 边翻四倍
addedge(int u, int v)
{
edge[++cnt] = {v, head[u]};
head[u] = cnt;
}