数据结构与算法_最近公共祖先LCA
最近公共祖先（Lowest Common Ancestors, LCA），是指在有根树中，某两个结点 u和 v最近的公共祖先。
祖先是指当前结点到树根的路径上所有的结点。
u 和 v的公共祖先是指一个结点既是 u 的祖先，又是 v 的祖先。
u 和 v 最近的公共祖先是指离 u 和 v 最近的公共祖先。
如果 v 本身就是 u 的祖先则 u 和 v 最近的公共祖先就是 v ，如图所示。
可以利用 LCA求解树上任意两点之间的距离。
例如，求 u 和 v之间的距离，如图所示。如果u和v的最近公共祖先为 lca,则 u 和 v之间的距离为 u 到树根的距离加上 v到到树根的距离，减去 2倍的 lca到树根的距离：
dist[u] + dist[v] -2*dist[lca]
求解 LCA的方法有很多，包括 1. 暴力搜索法， 2. 树上倍增法， 3. 在线 RMQ算法，4. 离线 Tarjan算法，5. 树链剖分法。本节只讲前 4种典型算法，树链剖分留到后面讲解。
在线算法：以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经直到所有的输入，在解决一个问题后立即输出结果。
离线算法：在开始时就需要知道问题的所有输入数据，可以一次性回答所有的问题。
除了离线Tarjan算法, 其它算法均为在线算法。
1. 暴力搜索法有两种思路：
第一种是向上标记法：从 u 向上一直到根结点，标记所有经过的结点；如果 v已经被标记，则 v 结点即为 LCA(u,v) 。否则 v 也向上走，第一次遇到已标记的结点时，该结点即为 LCA(u,v) 。
第二种是同步前进法：将 u,v中深度较深的那个结点向上走到和深度较浅的结点同一深度，然后两个点一起向上走，直到走到同一结点，该结点就是 u，v 的最近公共祖先，记作 LCA(u,v) 。如果较深的结点 u 到达 v 的同一深度时，那个结点正好就是 v, 则 v 结点即为 LCA( u,v ) 。
性能分析：
暴力搜索法求解 LCA,两种思路的时间复杂度最坏的情况下均为 O(n) 时间，每一次查询需要 O(n) 时间。
2. 在树上进行倍增
树上倍增法不仅仅可以解决 LCA问题，还可以解决很多其它问题，掌握树上倍增法的思路，是很有必要的。
F[ i，j ] 表示 i 的 2^j 辈祖先，即 i 结点向根结点走 2^j 步到达的结点。
例如，u 结点向上走 2^0 步，则为 u 的父亲 x，F[u,0] = x; u 结点向上走 2^1 步，到达 y , F[u,1] =y; 向上走 2^2步，达到 z, F[ u, 2] = z; u 结点向上走 2^3 步，结点不存在，令 F[u,3] = 0。如图所示：
1) 采用动态规划的思想，先填写二维表格
算法代码：
2）然后利用 ST 表，求解 LCA
和前面暴力搜索中第二种同步向前进法一样，先让深度大的结点 y 向上走到与 x 同深度，然后 x和y 一起向上走。和暴力搜索不同的是，向上走是按照倍增思想走的，不是一步一步地向上走，因此速度比较快。
怎么让深度大的结点 y 向上走到与 x 同深度呢？
总结：按照增量递减地方式，到达的结点深度比 x 的深度小时，什么也不做；到达的结点深度大于等于 x 的深度时，y 上移，直到增量为 0，此时 x,y 在同一深度。
算法代码：
x 和 y 一起向上走，怎么找最近公共祖先结点呢？
总结：按照增量递减的方式，到达的结点相同时，什么也不做；到达的结点不同时，同时上移，直到增量为0，此时 x,y 的父结点即为公共祖先结点。
算法代码：
性能分析：
3. 在线 RMQ 算法
两个点的 LCA 一定是两个点之间的欧拉序列（dfs 序列）中深度最小的那个点，寻找深度最小值可以使用 RMQ。
欧拉序列是指在深度遍历过程中，把依次经过的结点记录下来，回溯时经过的顶点也记录下来，一个结点可能被记录多次。相当于从树根开始，一笔画出一个经过所有点的回路。
该树的欧拉序列为 1 2 4 6 8 6 4 2 5 7 5 2 1 3 1 ，搜索时首先得到 6 和 5 的存储下标 i, j ,然后查询该区间深度最小的结点，即为 6和5号结点的最近公共祖先。
性能分析：
4. 离线 Tarjan 算法
这里的 Tarjan 算法是用于解决 LCA 问题的离线算法，你可能还会见到其他的 Tarjan算法，例如求连通分量的Tarjan算法。
在线算法是指每读入一个查询（求一次LCA叫做一次查询），运行一次程序得到本次查询答案，如果一次查询需要 O(log n)时间，m 次查询需要 O(mlogn); 离线算法是指首先读入所有的询问，然后运行一次程序得到所有查询答案。 Tarjan 算法利用并查集优越的时空复杂度，可以实现 LCA问题的线性处理时间 O(n+m)。
Tarjan 算法步骤：
