《C++入门到入土》——LCA树链剖分
前置必看
上回书说到，彼时的LCA，海中有一个玄学的做法，名为树剖，全名树链剖分。
首先声明定义:
重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；
树剖的核心思想，就是把一棵树分为数条不相交的轻重链。
我们定义，对于一个节点x来说，size[x]代表x的子节点个数。
对于每个节点x，我们选择其子节点y，使得size[y]>=size[z](z为x的任意子节点)。
此时x便有一条重边指向y，多条轻边指向其他子节点。上图：
如图，用黑线连接的结点都是重结点，其余均是轻结点，
2-11就是重链，2-5就是轻链，用红点标记的就是该结点所在重链的起点，也就是下文提到的top结点，
同时我们可以观察到：
对于任意一个结点的轻儿子，这个轻儿子是另一条重链的开头。即除根节点以外的重链开头的父结点都在重链上。
不在重链上的叶子节点独自构成一条重链（但写题时不要叶子结点的重儿子设为自己，会引起不必要的麻烦）。
所以轻链本质上就是用来连接不同的重链的。在清楚轻重链的定义之后，我们就可以开始进行一些神（xuan）奇（xue）的操作了——
先定义以下几个数组：
siz[i]=j：节点i的子树个数为j
son[i]=j：节点i的重链指向j
top[i]=j：节点i所在的重链开头为j
dep[i]=j：节点i的深度为j
fa[i]=j：节点i的父亲节点为j
首先进行初始化，这个过程需要两个dfs进行。
第一个dfs，初始化siz、fa、dep、son数组：
第二个dfs，利用刚刚的fa、son数组初始化top数组：
然后，我们通过观察推理可以得出：
若询问的两个节点x，y在同一条重链上，那么深度较小的那个点就是我们要求的公共祖先。
若不在同一条重链上呢？
我们可以直接跳到x、y所在重链的开头的父亲fx和fy，然后比较fx和fy的深度。若fx<fy，就让y跳到fy的位置，反之亦然。
这样一来，我们就可以不断向上跳到新的重链上，直到这两个节点在同一重链上（最坏情况就都跳到根节点上呗）
以上就是利用树剖实现LCA听说常数比倍增小
以下是全部代码：
玄学玩意总算完了
本质上树剖也是暴力优化，类似隔壁的分块，但时间复杂度还是挺优秀的（听说还能加上线段树用）
完结撒波奇酱~
祈愿心海和崩崩小圆帽
