一、定义
LCALCALCA 指的是最近公共祖先。一般来说，假如有一棵有根树，存在结点 xxx 和结点 yyy，若结点 zzz 是结点 xxx 的祖先，也是结点 yyy 的祖先，则称结点 zzz 为结点 xxx 和结点 yyy 的公共祖先。这 222 个结点深度最大的公共祖先被称为最近公共祖先，记为 LCA(x,y)LCA(x,y)LCA(x,y) 。
如图，若结点 111 为根结点，则 LCA(3,5)=2LCA(3,5)=2LCA(3,5)=2，LCA(5,6)=1LCA(5,6)=1LCA(5,6)=1 。
二、求解 LCALCALCA
我们首先考虑如何“暴力”求解 222 个结点的 LCALCALCA 。
容易想到，可以先 DFSDFSDFS 一遍找出每个结点的深度 deepdeepdeep，如果要求 LCA(2,6)LCA(2,6)LCA(2,6)，先从深度大的结点 666 往上跳至其父结点 444，发现深度与结点 222 一样了，但还是不在同一个结点，此时结点 222 和结点 444 一起往上跳，到达共同的父结点 111，得到 LCA(2,6)=1LCA(2,6)=1LCA(2,6)=1 。
但是这个方法在最坏情况下时间复杂度为 O(n)O(n)O(n)，数据规模大时容易 TLETLETLE 。
三、优化暴力
仔细思考便会发现，这个方法慢就慢在是一步一层往上跳的，如果能一步往上多跳几层，效率自然就高了。
我们采用树上倍增法，设 f[x][k]f[x][k]f[x][k] 表示结点 xxx 的 2k2^k2k 辈祖先，即从结点 xxx 出发向根结点走 2k2^k2k 步到达的结点。若该结点不存在，则另 f[x][k]=0f[x][k]=0f[x][k]=0 。这类似于动态规划，状态转移方程为 f[x][k]=f[f[x][k−1]][k−1]f[x][k]=f[f[x][k-1]][k-1]f[x][k]=f[f[x][k−1]][k−1]，边界条件即 f[x][0]f[x][0]f[x][0] 为结点 xxx 的父结点。
以上是预处理，时间复杂度为 O(nlogn)O(nlogn)O(nlogn)，之后对于每个 LCA(x,y)LCA(x,y)LCA(x,y)，都可以在 O(logn)O(logn)O(logn) 时间内计算出来。
基于 fff 数组计算 LCA(x,y)LCA(x,y)LCA(x,y) 分为以下几步：
1. 设 dep[x]dep[x]dep[x] 表示结点 xxx 的深度，可令 dep[x]≥dep[y]dep[x]≥dep[y]dep[x]≥dep[y] （否则就交换 xxx 和 yyy）
2. 接下来，依次尝试令 k=2log n,2log n−1,...,21,20k=2^{log\ n},2^{log\ n-1},...,2^1,2^0k=2log n,2log n−1,...,21,20，直到满足 dep[f[x][k]]≥dep[y]dep[f[x][k]]≥dep[y]dep[f[x][k]]≥dep[y]，令 x=f[x][k]x=f[x][k]x=f[x][k]
3. 若此时 x=yx=yx=y，则 LCA(x,y)=xLCA(x,y)=xLCA(x,y)=x，否则，依次尝试令 k=2log n,2log n−1,...,21,20k=2^{log\ n},2^{log\ n-1},...,2^1,2^0k=2log n,2log n−1,...,21,20，直到满足 f[x][k]≠f[y][k]f[x][k]≠f[y][k]f[x][k]=f[y][k]，令 x=f[x][k],y=f[y][k]x=f[x][k],y=f[y][k]x=f[x][k],y=f[y][k]，这时 xxx 和 yyy 必定只差 111
步便相遇了，LCA(x,y)=f[x][0]LCA(x,y)=f[x][0]LCA(x,y)=f[x][0] 。
具体代码实现如下：
参考资料《信息学奥赛一本通 · 提高篇》，本人水平有限，如有疑问，欢迎指正！
