介绍
解决树上问题的时候，对于路径问题我们会想到树分治、启发式合并。对于子树问题我们会想到在 dfs 序上转化为序列问题方便维护。
那么对于路径问题，能不能也转化为序列问题？
可以的。
这就是树链剖分在做的事情：把一棵树划分为若干段 dfn 连续的区间，使得某一个路径可以被拆分为 \(O(\log n)\) 个 dfs 序区间。（为了方便这里把拆出来的叫区间，原来的路径叫链）
虽然一开始给你的树不一定能够做到这一点，但是我们对 dfs 的顺序进行改变，可以做到这一点。考虑每次 dfs 到一个节点之后优先向其重儿子去遍历。
我们来证明一下上面的两个结论正确性。
首先，一棵树被划分为段 dfn 连续的区间：显然，某一个节点和父亲不连续说明它不是重儿子，于是不会被分到一起。
其次，一条路径被划分为 \(O(\log n)\) 段链：首先考虑某个点到根节点的路径。考虑现在有一个从 \(1\) 开始朝着另一端行走的人，它跳到另一个区间上花费 \(1\) 的代价。考虑其子树大小，每次一定减去至少一半。因此一共花费 \(O(\log n)\) 的代价。再考虑一般的路径，显然和其同阶。
考虑我们如何找到这些拆成的区间。我们有初始节点 \((x,y)\) 代表链的两端。然后不断选择所在区间深度较大的那一个点（假设是 \(x\)），找到链顶 \(top\)，对 \((top, x)\) 区间做贡献，然后 \(x\) 跳到 \(top.fa\)。注意区间深度指的是根节点到这条链要穿过几条链，因为如果使用的是点的深度，那么上图的 \(5 \rightarrow 8\) 因为 \(5\) 深度较大要跳，但是它已经不能再跳了。
伪代码：
void gx(int x, int y) {
while(1) {
if(x.belong.deep < y.belong.deep) swap(x,y);
if(x.belong != y.belong) {
update(x.belong.top, x); //dfn 连续段
x = fa[x.belong.top];
}
else break;
}
if(x.depth > y.depth) swap(x, y);
update(x, y);
}
如何进行树剖
考虑需要维护什么。
- 子树大小 -> 重儿子。
- dfs 序，以及每个 dfs 序对应什么节点。
- 每个节点属于什么链上。
- 链顶和底。
- 每条链的深度。
- 点的深度。
- 点的父亲。
做两次 dfs 进行维护。
第一次 dfs 维护什么：
- 子树大小 -> 重儿子。
- 点的深度。
- 点的父亲。
第二次 dfs 维护什么：
- dfs 序，以及每个 dfs 序对应什么节点。
- 每个节点属于什么链上。
- 链顶和底（但是我们发现好像不太需要维护链底）。
- 每条链的深度。