『复习笔记』树链剖分（重链剖分）
前言（事出必有因）
今天模拟赛有一道线段树+LCA的题，考场上码了两个小时，结果pushup错了，结果线段树调完了，发现TLE了，原来是求LCA炸了。。
因为我用的倍增（我就是倍增狗你能把我怎么样），但是倍增的一个重要问题就是log都跑满了，但是树剖跑不满log，别问我为什么不用Tarjan，因为这题是在线的不好搞，还有一个ST表求LCA的但是我很菜不会啊~
上正文
树剖（重剖）就是把一棵树剖成若干条重链，从而求解有关树上问题。
树剖的一些基本概念，比如说轻重儿子，轻重链啥的自己都知道就不写了，就算忘了应该也能想起来。
树剖的性质：
-
对于一棵树，每一个点都属于一条重链（如果我们把剖剩下的叶节点也算一条重链的话）。
-
每个点最多有一个重儿子。如果这个点只有一个儿子，那么这个点一定是重儿子。显然，叶节点没有（重）儿子。
-
每条重链上的节点的 dfs 序是连续的。
-
如果有什么遗漏，那么以后碰到了想起来了再补充，或者大家在评论区里指出来，蒟蒻感激不尽。orz。
树剖（重剖）基本上分为两部分：
-
第一部分是预处理，两遍dfs。
-
第一遍求出重儿子，深度（距离），每一个节点的父节点，以及每一个子树大小。
-
第二遍求出dfs序（树上区间），反dfs序，以及每条重链的链头。
-
-
第二部分是跳链。这可以求解一些问题，诸如求LCA（这个直接跳链就可以），求链上最值，区间和，区间积（这些需要用像线段树这样的数据结构维护）等等。
-
对于两个节点，我们先比较它们的链头的深度，如果某个节点链头的深度较大，那么就跳到链头的父节点上。直到它们都跳到了一条链上。
-
在这个过程中我们可以以一条链为单位求解树上某条链的信息。当然我们也可以不维护任何信息求解LCA。
-