最近公共祖先

百科名片

• 最近公共祖先
• Lowest Common Ancestors
• LCA

简单引入

对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。

红色的都是是A和B的公共祖先，但只有最近的C才是最近公共祖先。

LCA问题是树上的一个经典问题，在很多方面有着广泛的应用，比如求LCP（最长公共前缀），接下来我们就来介绍他的几种算法。

LCA的算法

暴力枚举法

如果我们要求a和b的最近公共祖先，就沿着父亲的方向把a的所有祖先都标记
一下（类似并查集找父亲，但是没有路径压缩），然后在从b开始往上找祖先，
碰到第一个被标记的点，就是a和b的最近公共祖先。

C是最近公共祖先。

求一个对点的LCA时间复杂度高达O（N）。
求m个点对的LCA时间复杂度高达O（mN）。
当m和n都高达10万的时候，超时了！！！

宝宝难以承受！！！！！

求m个点对的最近公共祖先是可以优化的，一般有两种：
1、离线算法（Tarjan离线算法）：所谓的离线算法指的是把所有问题收集起来以后一起去算，最后一起回答。
2、在线算法（倍增算法）：所谓的在线算法就是来一个点对，处理一个点对。

Tarjan离线算法

Robert Tarjan设计了求解的应用领域的许多问题的广泛有效的算法和数据结构。 他已发表了超过228篇理论文章（包括杂志，一些书中的一些章节文章等）。Robert Tarjan以在数据结构和图论上的开创性工作而闻名。 他的一些著名的算法包括 Tarjan最近共同祖先离线算法 ，Tarjan的强连通分量算法等。其中Hopcroft-Tarjan平面嵌入算法是第一个线性时间平面算法。Tarjan也开创了重要的数据结构如：斐波纳契堆和splay树（splay发明者还有Daniel Sleator）。另一项重大贡献是分析了并查集。他是第一个证明了计算反阿克曼函数的乐观时间复杂度的科学家。

简单的介绍一下tarjan算法：
tarjan算法是离线算法，它必须先将所有的要查询的点对存起来，然后在搜的时候输出结果。
tarjan算法很经典，因为算法的思想很巧妙，利用了并查集思想，在dfs下，将查询一步一步的搜出来。

基本思路：
1 任选一个节点为根节点，从根节点开始
2 遍历该点 u 的所有子节点 v ，并标记 v 已经被访问过
3 若 v 还有子节点，返回 2 ，否则下一步
4 合并 v 到 u 所在集合
5 寻找与当前点 u 有询问关系的点 e
6 若 e 已经被访问过，则可以确定 u、e 的最近公共祖先为 e 被合并到的父亲节点

• 对于我们已经保存好的查询，假设为(u,v)，u为此时已经搜完的子树的根节
  点，v的位置就只有两种可能，一种是在u的子树内，另一种就是在其之外。
• 对于在u的子树内的话，最近公共祖先肯定是可以直接得出为u。
• 对于在u的子树之外的v，我们已经将v搜过了，且已经知道了v的祖先，那么我们可以根据dfs的思想，v肯定是和u在一颗子树下的，而且这颗子树是使得他们能在一颗子树下面深度最深的。而这个子树的根节点刚好就是v的并查集所保存的祖先。所以对于这种情况的(u,v)，它们的最近公共祖先就是v的并查集祖先。

下面给出伪代码：

void Tarjan(u) {   // merge 和 find 为并查集合并函数和查找函数	for each(u,v) {     // 遍历 u 的所有子节点 v		Tarjan(v);      // 继续往下遍历merge(u,v);     // 合并 v 到 u 这一集合标记 v 已被访问过;	}for each(u,e) {       // 遍历所有与 u 有查询关系的 eif(e 被访问过)u, e 的最近公共祖先为 find(e);}
}

下面给出真代码：

int f[N],n,m,ans[N],check[N]; 
vector<int> a[N],b[N],id[N]; int find(int x) { return x==f[x] ? x : f[x]=find(f[x]); }void tarjan(int x) {f[x]=x; check[x]=1; for(int i=0; i<a[x].size(); i++) {int v=a[x][i]; if(!check[v]) {tarjan(v);  f[v]=x; }}for(int i=0; i<b[x].size(); i++) {int v=b[x][i]; if(!check[v]) continue; ans[id[x][i]]=find(v); }
}

我们在深度优先遍历的时候，先遍历x节点的
左子树，当遍历到u的时候，发现v没有被遍历过，那么就不去管lca(u,v)这个问题，然后我们把已经遍历的x子树的所有节点都合并到他的父亲（即father指向父亲），然后当我们遍历到v的时候，发现u已经遍历过了，那么此时u在并查集里的father就是u和v的最近公共祖先.

时间复杂度：由于每个点只遍历一次，每个问题只枚举2次，所以时间复杂度是O（N+2Mα(N))。α(N)为并查集查询一次根所需要的时间。

未完待续……