最近公共祖先 LCA 问题

LCA (Lowest Common Ancestor)：

给定一棵有根树，若节z既是节点x的祖先，也是节点y的祖先，则称z是x，y的公 共祖先。在x，y的所有公共祖先中，深度最大的一个称为 x，y的最近公共祖先，记为LCA(x,y)。

如图

树的最近公共祖先问题是树结构上最经典的问题之一

LCA问题的算法分为离线算法（并查集+DFS）和在线算法(RMQ+DFS) 两种，前者允许在读入所有询问之后一次性给出所有问题的答案，而在线问题要求在回答后一个问题之前必须给出前一个问题的答案。

LCA问题的应用很多，例如它可以用来回答这样的询问 “点u和点v的距离是多少？”，由于在树中两点的简单路是唯一的，所以这个距离等于u到LCA(u,v)再到v的距离，即d[u]+d[v]-2*d[LCA(u,v)]。

离线LCA——Tarjan算法

由于这个算法在竞赛中使用极少，这里不多说

算法思想：

1. 从u向上走到根节点，并标记所有经过的节点。

2. 再从v向上走到根节点，当第一次遇到已标记的节点时，就找到了LCA(u,v)。

解决LCA问题的Tarjan算法利用并查集在一次DFS中完成所有询问，时间复杂度为O(Na(N)+Q)

举例说明：

在线LCA——树上倍增法（又称爬树法）

算法步骤：

预处理

设d[i]表示i点的深度， p[i,j] 表示i的2^j倍祖先，使用类似 RMQ 的 ST算法，递推式为 p[i,j]=p[p[i,j-1],j-l]。 可以在 O(NlogN) 的时间内预处理求出每个节点的2^j的祖先。

然后对于每一个询问的点对a，b的最近公共祖先就是：

1. 先判断是否 d[a]<d[b]，如果是的话就交换一下（保证a的深度大于b，方便下面的操作）。其中d[a]表示结点a在树中的深度。
2. 再把a爬到与b同深度（先大步后小步思想）
3. 再把a,b同时往上爬，要求k满足 p[a,k]≠p[b,k]，改变 a=p[a,k],b=p[b,k]，然后继续调整。
4. 最后 p[a,0] 或 p[b,0] ，即为最近公共祖先