树链剖分

• 树链剖分
  • 重链剖分
    • 定义申明
      • 注意：
    • 实现
  • 附：链式前行星代码

重链剖分

树链剖分：将树分割成若干条链的形式，用于维护树上的信息。

形式：

• 重链剖分
• 长链剖分
• 实链剖分
• 等等

重链剖分由于将树上数据的维护变成了序列数据的维护，因此可以用线段树等维护序列的数据结构便捷地维护。

定义申明

1. 重儿子（Heavy Son）：对于一个节点 u，其所有子节点中子树大小最大的那个子节点称为重儿子。如果有多个最大，任意选一个。
2. 轻儿子（Light Son）：除了重儿子以外的其他子节点。
3. 重边（Heavy Edge）：连接节点 u 和其重儿子的边。
4. 轻边（Light Edge）：连接节点 u 和其轻儿子的边。
5. 重链（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 序对应位置的节点权值。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。如图：

来源于OI-WiKi，侵删

注意：

节点编号有：

• 原编号（节点ID）
  • 范围：1 到 n
  • 用途：x, fa, edge[i].to 等都使用这个编号体系
  • 示例：根节点是1，它的子节点可能是2,3,4等
• DFS序编号 (tid)
  • 范围：1 到 n
  • 用途：线段树中的位置编号
  • 映射：tid[x] 表示原节点x的DFS序位置
• 边的索引 (edge下标)
  • 范围：1 到 cnt（边的计数器）
  • 用途：邻接表中遍历边时使用

实现

共用两个DFS：

1. 信息收集

   目的： 计算每个节点的基础信息，为后续剖分做准备。

   获得了以下基础信息：

   • 每棵树的子树大小
   • 标记父节点和深度
   • 确定重儿子

   具体步骤：

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

2. 划分重链并生成DFS序

   核心逻辑:

   1. DFS序分配 (tid[])
      • 每个节点被访问时获得一个唯一的DFS序编号
      • 关键技巧：先递归重儿子，保证同一条重链上的节点编号连续
   2. 重链划分 (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);
           }
       }
   }
   

附：链式前行星代码

// 链式前向星
struct Node {
    int to, next;
//  int w; //权重
} edge[maxn << 2]; // 边翻四倍

addedge(int u, int v) 
{
    edge[++cnt] = {v, head[u]};
    head[u] = cnt;
}