P3379 【模板】最近公共祖先（LCA）
本题中的树链剖分均指重链剖分。
这里不使用重链剖分作为模板是因为这道题更加典型，不需要使用额外的数据结构，就是纯天然、无污染的树剖（我诗兴大发喝多了）。
首先，树剖是一个思想，可以将树上两点路径的问题转变为一个序列上，不超过 \(O(\log n)\) 段的问题，这就给了树状数组、线段树等一系列数据结构解决树上路径问题的方式。
切入正题，树剖到底是什么呢。
直接上图
重子节点为其父节点的子节点中中子树大小最大的节点（有一样的选一个即可），轻子节点为除其父节点的重子节点外的其他子节点。重边指下面连接重子节点的边。轻边则为除重子节点外的边。
重链就是由若干段连续重边组成的路径。
然后我们再做一遍 dfs，优先遍历每个点的重子节点，然后可以得到右边图的 DFN 序。这样遍历保证了每段重链上的点的编号均连续。
又有一个定理：对于树上任意一条路径，都能拆分成 \(\log n\) 条重链。
因为你只要走一条轻边，那么子树大小至少减小一半，而每进入一条重链都需要走一条轻边，所以就是 \(O(\log n)\) 的复杂度。
对于本题，尽管求的是 LCA，我们一般用朴素的倍增算法求解，但是也可以使用树链剖分（常数更小）。
对于两个点，每次优先让所在重链顶端的点深度更深者跳到重链顶端的父亲。然后直到两者在一条链上停止。最终深度较小者为 LCA。
简单证明的话，只要两个点不在一个重链上，那么肯定没有到达 LCA，而一旦汇合，那么这个点肯定是第一个汇合的点（因为本来在两条链上，你突然有一个点跳到了另外这条链上，那么第一个汇合的位置就是这里了）。
尽管代码稍微比倍增写法长，但是好写常数小。