LCA 的 $n$ 种求法。
LCA 是许多树上问题的基础。
本文将介绍 LCA 的 $5$ 种求法。
倍增：
先考虑什么是倍增。
对于一个 $x$，其一定能被拆分成若干个 $2$ 的整数幂次之和（二进制描述），同时一个拆分策略就是每次减去不超过 $x$ 的最大 $2$ 的整数幂次。
考虑在一个二分问题上（解序列满足单调性），比 $x$ 大的值均为解。所以每次加上一个最大的无解的 2 的整数幂次，最后一定可以得到 $x$。
观察到：LCA 的性质是“最近”，而当距离超过这个“最近”后，到根所有的祖先节点均为 $(x,y)$ 的 CA。即：满足二分性。一般在树上问题，二分实现较麻烦，不如倍增。
设 f$[x][i]$ 表示 $x$ 的 $2^i$ 级祖先。
先要将 $x,y$ 跳到同一深度，否则相同的 $i$，$x,y$ 的 $2^i$ 祖先不相同无法倍增。解决方法同倍增，对于深度较深的点，若它的 $2^i$ 级祖先的深度已经低于另一个点了，那么就将 $i$ 减小。
那么从 $x$ 和 $y$ 分别往上跳祖先，当跳到一个相同点时，所以至少是 LCA 的祖先了，那么就可以将 $i$ 减小。
时间复杂度：$O(\log n)$。
需要预处理倍增数组和深度数组。
通常作为最经典、最广的 LCA 求法被使用。
Tarjan：
考虑 $m$ 次询问 LCA$(x,y)$，Tarjan 求 LCA 是一种离线算法，通常使用并查集维护某节点的祖先节点。
使用并查集的 Tarjan 时间复杂度为：$O(m\alpha(n+m)+n)$，但是存在严格 $O(m+n)$ 时间复杂度的 Tarjan 做法，但是 Tarjan 常数较大。
时间复杂度：$O(n)-O(1)$。
不常用。
欧拉序求 LCA：
引理 1：树上 $(x,y)$ 的路径在树的欧拉序中是连续的一部分。
引理 2：树上 $(x,y)$ 不在 $(x,y)$ 路径上的祖先不在 $(x,y)$ 欧拉序中。
所以求 $(x,y)$ 的 LCA 等价于求 $(x,y)$ 欧拉序（并不关心 $x,y$ 欧拉序第几次出现的位置，只要保证之间不存在 LCA 的祖先即可）上深度最小的点。
转换成了静态区间询问最小值位置的问题，使用任何喜欢的方式维护即可。
因为是静态的，所以一般使用 ST 表维护。
时间复杂度：$O(n\log n)-O(1)$。
dfs 序求 LCA：
引理：树上的某子树的点在 dfs 序中是连续的一部分。
所以 $x,y$ 的子树 dfs 序一定是在 LCA 的子树中，且在从 x/y 回溯到 y/x（取决于谁在 dfs 序中位置更靠前）的过程中，一定会经过 LCA 的某个儿子。
所以求出 $x,y$ 的 dfs 序中的深度最小值，LCA 即为该点的父节点。
时间复杂度同欧拉序求 LCA。
dfs 序求 LCA 相比欧拉序求 LCA 而言，优势在于 dfs 序点数更少（dfs 序记录 $n$ 个点，欧拉序记录 $2n-1$ 个点）dfs 序扩展性相对更强，在题目中同时需要求其它内容时，具有兼容性。
树链剖分求 LCA：
此处指重链剖分。
与倍增相似，每次把 $x,y$ 向上跳到链顶位置，跳到相同的点时，说明找到了。因为链是连续的一段，所以最后的 LCA 就是不在链内的另一条链的链顶的父节点。
根据重链剖分性质，易得从 $x$ 到根节点最多经过 $O(\log n)$ 条链。
时间复杂度：$O(n)-O(\log n)$。且常数较小。
番外：
LCA 与 RMQ 问题。
RMQ 即：静态区间最值问题。
LCA 转换成 dfs 序/欧拉序上最值后，时间复杂度瓶颈为区间最值的瓶颈，而实际上 RMQ 存在 $O(n)$ 预处理 $O(1)$ 询问的算法。
同时，RMQ 问题也可转换为笛卡尔树上 LCA 问题。
树上 k 级祖先：
倍增、重链剖分均可在 $O(\log n)$ 的时间复杂度内解决。
使用长链剖分，可以在 $O(n)$ 的时间复杂度内解决。