【学习笔记】重链剖分

目录

• 1
  
  
  
  • 导论
    
  • DFS 序
    
    
    
    • 1.1 DFS回顾
      
    • 1.2 时间戳（Time Stamp）
      
      
      
      • 案例模拟
        
      
      
    • 1.3 进出时间戳（Entry and Exit Time）
      
    
    
  • 第 2 章：子树映射
    
    
    
    • 2.1 为什么子树一定是连续的？
      
    • 2.2 映射关系的两种形式
      
      
      
      • 形式 A：入栈序 \(\rightarrow\) 子树区间
        
      • 形式 B：入出栈序（欧拉序）
        
      
      
    
    
  • 第 3 章：区间操作实现
    
    
    
    • 3.1 转换表
      
    • 3.2 细节
      
    
    
  • Code
    
  • DFS 序 + 树状数组（P2800）
    
  • P1689 / P3099
    
    
    
    • 1. 为什么 sz 这么重要？
      
    • 2. 复杂度分析
      
    • 3. 常见 Bug 检查清单
      
    
    
  
  
• 2
  
  
  
  • 重链剖分
    
    
    
    • 1.1 路径查询？
      
    • 1.2 重儿子（Heavy Son）的定义
      
    • 1.3 核心定理：跳跃次数上限
      
    
    
  • 两次 DFS
    
    
    
    • 2.1 第一次 DFS（预处理）
      
    • 2.2 第二次 DFS（打平）
      
    
    
  • 路径跳跃算法 (HLD Query)
    
    
    
    • 3.1 跳链逻辑
      
    • 3.2 复杂度分析
      
    
    
  • 代码实现（以 P1722 为例）
    
  • 题目...
    
    
    
    • 5.1 P1723 [SDOI2011] 染色
      
    • 5.2 P3580 [HAOI2015] 树上操作
      
    • 1. 逻辑链条
      
    
    
  • 配合&决策
    
    
    
    • 3.1 核心判别法
      
    • 3.2 综合题型分析示例
      
    
    
  • 一些本质
    
  
  

1

导论

在计算机科学中，我们处理线性结构（如数组、字符串、链表）是非常高效的。因为线性结构拥有一个极其强大的特性：连续性。有了连续性，我们就可以使用前缀和、双指针、线段树、树状数组等工具，在 \(O(\log N)\) 甚至 \(O(1)\) 的时间内完成区间操作。
然而，树（Tree）是一种典型的非线性结构。它具有层级关系，节点之间通过边连接。如果你想查询“以节点 \(u\) 为根的子树内所有节点的权值之和”，在原始的树结构中，你必须通过递归（DFS）遍历整个子树，时间复杂度是 \(O(SubtreeSize)\)。在最坏情况下（树退化成一条链），单次查询需要 \(O(N)\)。
那么，有没有一种方法，能把一棵“立体”的树，“拍扁”成一条“平面”的线，且在拍扁的过程中，依然能够保持子树的连续性？
这就是 DFS 序（DFS Order） 的核心目的。
DFS 序

1.1 DFS回顾

在进入 DFS 序之前，请你在脑海中重新运行一次 DFS 的过程。
当我们从根节点 \(r\) 开始 DFS 时，算法的行为是：尽可能深地探索，直到无法继续，然后回溯。
这个过程在内存中是由递归栈（Call Stack）维护的。一个节点 \(u\) 被访问时，它会被压入栈中；只有当 \(u\) 的所有子节点都被全部访问完毕后，\(u\) 才会从栈中弹出。
1.2 时间戳（Time Stamp）

为了记录 DFS 的轨迹，我们引入一个全局计数器 timer（初始值为 0）。
每当我们第一次进入一个节点 \(u\) 时，我们将当前的 timer 赋值给 \(u\)，然后 timer 自增 1。这个值就叫做节点的 DFN 序（Depth First Number），记作 \(dfn\)。
案例模拟

假设有一棵简单的树：

• 1 是根，连接 2 和 3
  
• 2 连接 4 和 5
  
• 3 连接 6
  

DFS 遍历顺序可能是： \(1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 6\)
对应的 DFN 序：

• \(dfn[1] = 1\)
  
• \(dfn[2] = 2\)
  
• \(dfn[4] = 3\)
  
• \(dfn[5] = 4\)
  
• \(dfn[3] = 5\)
  
• \(dfn[6] = 6\)
  

1.3 进出时间戳（Entry and Exit Time）

仅仅记录进入时间 \(dfn\) 是不够的，因为我们不知道一个子树在什么时候“结束”。
因此，我们引入出栈时间戳 \(out\)：当我们完成对节点 \(u\) 及其所有子树的访问，准备从 \(u\) 回溯到其父节点之前，我们记录当前的 timer。
修正后的模拟：

• 进入 1：\(dfn[1]=1\), timer \(\to\) 2
  
• 进入 2：\(dfn[2]=2\), timer \(\to\) 3
  
• 进入 4：\(dfn[4]=3\), timer \(\to\) 4
  
• 离开 4：\(out[4]=4\), timer \(\to\) 5 (注：有些实现中 timer 不在离开时增加，这里我们采用增加方案以便更清晰地界定区间)
  ... 以此类推。
  

关键结论：
对于任何节点 \(u\)，它的所有后代节点 \(v\) 满足：

\[dfn \le dfn[v] \le out\]
这意味着：在 DFS 序的线性数组中，节点 \(u\) 的子树被完美地映射为了一个连续的区间 \([dfn, out]\)。
第 2 章：子树映射

2.1 为什么子树一定是连续的？

这是一个非常关键的逻辑点，初学者必须彻底理解。
证明思路：
DFS 的特性是“先深后广”。当你进入节点 \(u\) 时，在 DFS 算法离开 \(u\) 之前，它绝对不会访问任何不属于 \(u\) 子树的节点。

• 所有的子节点 \(v_1, v_2, \dots\) 必须在 \(u\) 进入之后被访问。
  
• 所有的子节点及其后代必须在 \(u\) 离开之前被访问完毕。
  
• 因此，在 timer 的时间轴上，从 \(dfn\) 到 \(out\) 之间出现的所有时间戳，全部且仅属于 \(u\) 的子树。
  

2.2 映射关系的两种形式

在实际竞赛中，你会看到两种主流的 DFS 序记录方式：
形式 A：入栈序 \(\rightarrow\) 子树区间

• 只记录 \(dfn\)。
  
• 记录每个子树的大小 \(sz\)。
  
• 子树区间为 \([dfn, dfn + sz - 1]\)。
  
• 适用场景：大多数树链剖分、子树求和问题。
  

形式 B：入出栈序（欧拉序）

• 同时记录 \(dfn\) 和 \(out\)。
  
• 子树区间为 \([dfn, out]\)。
  
• 适用场景：需要处理节点进入和离开不同操作的问题（如某些复杂的树形 DP）。
  

第 3 章：区间操作实现

既然子树变成了区间，那么原本复杂的“树上操作”就变成了简单的“区间操作”。
3.1 转换表

树上操作线性映射后操作推荐数据结构时间复杂度修改节点 \(u\) 的权值修改数组中 \(dfn\) 位置的值树状数组 / 线段树\(O(\log N)\)查询子树 \(u\) 的权值和查询区间 \([dfn, dfn+sz-1]\) 的和树状数组 / 线段树\(O(\log N)\)修改子树 \(u\) 所有权值 \(+v\)区间修改 \([dfn, dfn+sz-1]\)线段树 (Lazy Tag)\(O(\log N)\)3.2 细节

• 递归深度：对于 \(N=10^5\) 的数据，默认栈空间可能不足。在 C++ 中，可以使用 #pragma comment(linker, "/STACK:1024000000") 或在 Linux 下使用 ulimit -s unlimited。
  
• 邻接表顺序：DFS 遍历子节点的顺序不影响子树连续性，但会影响具体的 \(dfn\) 值。在对比答案时，请确保遍历顺序一致。
  
• 1-indexed vs 0-indexed：建议 \(dfn\) 从 1 开始，因为树状数组（BIT）不支持 0 号下标。
  

Code

学会如何把一棵树拍扁成一个数组。
[code]#include #include #include using namespace std;const int MAXN = 100005;vector adj[MAXN]; // 邻接表存储树int dfn[MAXN];         // 记录节点 u 第一次被访问的时间戳int sz[MAXN];          // 记录以节点 u 为根的子树大小int rev[MAXN];         // 逆映射：dfn = x  ==> rev[x] = uint timer = 0;         // 全局时间戳计数器// 核心 DFS 函数void dfs(int u, int fa) {    // 1. 记录进入时间戳    dfn = ++timer;     rev[timer] = u;    // 记录这个时间戳对应的是哪个节点    sz = 1;         // 初始子树大小为 1（节点本身）    for (int v : adj) {        if (v == fa) continue; // 防止在无向图中跑回父节点              dfs(v, u);             // 递归进入子节点              // 2. 关键：子树大小是所有子节点子树大小之和 + 1        sz += sz[v];     }    // 此时，节点 u 的子树在 dfn 数组中的区间是 [dfn, dfn + sz - 1]}int main() {    int n; cin >> n;    for (int i = 0; i < n - 1; i++) {        int u, v; cin >> u >> v;        adj.push_back(v);        adj[v].push_back(u);    }    dfs(1, 0); // 从根节点 1 开始，父节点设为 0    cout  val;            // 计算增量，因为 BIT 是累加更新            int diff = val - weight;            weight = val;             update(dfn, diff); // 修改 dfn 位置的值        } else { // 子树查询            int u; cin >> u;            // 子树 u  ==>  区间 [dfn, dfn + sz - 1]            cout  opt;        if (opt == 1) { // 子树修改            int u, val; cin >> u >> val;            update(1, 1, n, dfn, dfn + sz - 1, val);        } else { // 子树查询            int u; cin >> u;            cout  m;    for (int i = 1; i > weight;    for (int i = 0; i < n - 1; i++) {        int u, v; cin >> u >> v;        adj.push_back(v); adj[v].push_back(u);    }    dfs1(1, 0, 1);    dfs2(1, 1);    // 初始化线段树：将原权值填入 dfn 序位置    for (int i = 1; i > op >> u >> v;        if (op == 1) {            cin >> w;            update_path(u, v, w, n);        } else {            cout