最近公共祖先
百科名片
- 最近公共祖先
- 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 有查询关系的 e
if(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)为并查集查询一次根所需要的时间。
未完待续……