1. 重链剖分
1.1. 简介
重链剖分将树分割成若干链维护信息，将树的结构转换为线性结构，然后可用其他数据结构维护。
定义以下概念：
| 重子节点 | 轻子节点 | 重边 | 轻边 | 重链 |
|---|---|---|---|---|
| 某节点的子节点中子树大小最大的那个 | 某节点的子节点中的非重子节点 | 由某节点到其重子节点的连边 | 由某节点到其轻子节点的连边 | 若干条头尾相接的重边构成的链（落单的节点也看作一个重链） |
重链剖分有以下性质：
- 剖分时优先遍历重边，于是一条重链上的 DNF 序连续。
- 一颗子树内 DFN 序连续。
根据这两条性质我们可以考虑维两节点路径上的信息，与一个子树内的信息。路径上的信息可以用若干重链信息拼接而成维护，子树内则直接用一定范围内连续 DFN 的节点信息维护即可。
重链剖分同时可以解决求 LCA 问题，当然，这在维护路径上信息时就需要用到。对于两个节点，考虑将深度大的节点跳转至其所在重链顶点的父节点，进行此操作若干次直到两者在一条重链上。最后一个一个跳转即可。
1.2. 具体实现
实现时，维护以下变量：
| \(fa_i\) | \(dep_i\) | \(siz_i\) | \(hson_i\) | \(top_i\) | \(dfn_i\) | \(rk_i\) |
|---|---|---|---|---|---|---|
| 节点 \(i\) 的父节点 | 节点 \(i\) 的深度 | 节点 \(i\) 的子树大小 | 节点 \(i\) 的重子节点 | 节点 \(i\) 所在重链顶点 | 节点 \(i\) 的 DFN 序 | DFN 序为 \(i\) 的节点编号 |
剖分操作需要进行两次 DFS：
- 第一次 DFS 维护 \(fa_i,dep_i,siz_i,hson_i\)。
- 第二次 DFS 维护 \(top_i,dfn_i,rk_i\)。