【算法笔记】最近公共祖先

「冥界の土地も有限よ、余計な霊魂は全て斬る！」

最近公共祖先(Lowest Common Ancestors)

定义1

我们假设有一颗有根树 \(T\)，对于 \(\forall x,y \in T\)。

一定存在至少一个节点 \(z \in T\) ,满足 \(z\) 是 \(x\) 的祖先 且 \(z\) 是 \(y\) 的祖先。

特别的，一个节点 \(x\) 的祖先也可以是 \(x\) 自己。

那么所有的 \(z\) 所组成的集合中 ，深度最大的一个 \(z\) 则称为 \(x,y\) 的最近公共祖先，一般记作 \(\texttt{LCA}(x,y)\)。

倍增Lca算法就基于这个定义。

定义2

是这样子的：

若存在一个无向无环图 \(T\)， 那么\(x \to y\) 的最短路上的深度最小的点就是 \(\texttt{LCA}(x,y)\)

注意，这个“深度最小” 还是从树的角度来说的。

Tarjan算法就基于这个定义。

图例：

如图所示，蓝点 \(x,y\) 的最近公共祖先是黄色点 \(\texttt{LCA}(x,y)\)

向上标记法求 LCA

考虑怎么来求 \(\texttt{LCA}\)。

首先第一个想法是根据定义1，我们从 \(x\) 向上搜索 \(x\) 的祖先，同时从 \(y\) 开始向上搜索 \(y\) 的祖先，搜到一个标记一个。

然后找出深度最大的被同时标记的节点 \(z\) ，\(z\) 就是 \(\texttt{LCA}(x,y)\)

（当然同时搜两个不太现实，我们一般是先让 \(x\) 搜到 \(root\) 之后用 \(y\) 来搜，找到的第一个被标记过得节点就是 \(\texttt{LCA}(x,y)\)）

但如果 \(T\) 是一个链而 \(x,y\) 分别在链的端点处，那么单次询问的复杂度就会被卡到 \(\text{O}(n)\) 。

对于多次询问,。

Tarjan求 LCA

这是候就有人要问了：“这个暴力能优化吗？”

看起来好像真的没什么办法。

但是 \(\texttt{Tarjan}\) 老爷子带着他的并查集跳了出来：

我能优化！

这是一个基于并查集和定义2的离线算法。

大概思路是 \(\texttt{dfs}\) 遍历树 \(T\)，利用并查集。

当某个节点 \(u\) 及其子树遍历完成后,处理所有和 \(u\) 有关的查询。

以此达到优化“向上标记法” 的目的。

标记的流程：

1. 假设我们当前访问到了节点 \(u\) , 那么我们新建一个关于 \(u\) 的集合 \(S\) （利用并查集）

2. 递归搜索 \(u\) 的子树，如果说 某一颗子树 \(v\) 被搜完了，我们标记 \(vis[v]=true\)

3. 很明显这个子树递归的过程当中也会产生一个新的集合 \(S^{'}\)，那么这时我们将 \(S\) 和 \(S^{'}\) 合并并且以 \(u\) 作为整个大集合的 \(root\) 。

4. 重复 2,3 ，直到 \(u\) 的所有子树都被访问完（即 \(vis\) 都被标记），这时将 \(vis[u]\) 标记为 \(true\)

这时候已经遍历完成了 \(u\) 以及 \(u\) 的所有子树，我们就可以处理查询了。

考虑一个查询 \((u,v)\) 。

• 如果说 \(vis[v]=true\) ,也就是已经被标记过了。

  那么 \(\texttt{LCA}(u,v)\) 就是 \(\texttt{root}(v)\) （并查集的查询根）

  为什么呢？

  因为 \(vis[v]=true\) 的话，根据上面的标记流程，我们可以知道，

  它带着它的子树此时一定被并到了它的父亲的集合里去，

  而它的父亲又有可能被合到它(\(v\))父亲的父亲的集合里。

  以此类推，搜到大集合的根的时候，这个根一定没被标记过，否则它也将会被并到它（根）的父亲（祖先）节点的集合里去。

  所以 \(\texttt{LCA}(u,v)\) 就是 \(\texttt{root}(v)\) 。（反证法）

• 如果说 \(vis[v]\not= true\)。

  那么跳过这个询问，当 \(v\) 和 \(v\) 的子树遍历完的时候一定会回来更新 \((u,v)\) 的（上一种情况）。

因为每个点只会别标记一次，每个询问也只处理一次。

所以复杂度为 \(\text{O}(n+q)\) （\(q\) 是查询次数）。

是所有\(\texttt{LCA}\) 的算法里面最快的。

Code：

#include
using namespace std;

#define pb push_back
const int si_n=5e5+10;
const int si_m=5e5+10;

struct Tree{
	int ver,Next,head;
}e[si_m<<1];
int cnt=0;
void add(int u,int v){
	e[++cnt].ver=v,e[cnt].Next=e[u].head;
	e[u].head=cnt;
}

int pa[si_n];
int root(int x){
	if(pa[x]!=x){
		return pa[x]=root(pa[x]);
	}
	return pa[x];
}
vectorque[si_n],pos[si_n];
int lca[si_n];
bool vis[si_n];
int n,q,s;

void tarjan(int u){
	vis[u]=true;
	for(register int i=e[u].head;i;i=e[i].Next){
		int v=e[i].ver;
		if(vis[v]==true) continue;
		tarjan(v),pa[v]=root(u);
	}
	for(register int i=0;i<(int)que[u].size();++i){
		int v=que[u][i],po=pos[u][i];
		if(vis[v]==true) lca[po]=root(v);
	}
}

int main(){
	scanf("%d%d%d",&n,&q,&s);
	for(register int i=1;i<=n;++i){
		pa[i]=i,vis[i]=false;
		que[i].clear(),pos[i].clear();
	}
	for(register int i=1;i

#include
using namespace std;

const int si=5e5+8;
int n,m,root;
struct Tree{
	int ver,head,Next;
}e[si<<1];
int cnt=0;
void add(int u,int v){
	e[++cnt].ver=v;e[cnt].Next=e[u].head;
	e[u].head=cnt;
}
int dep[si];
int f[si][20];

void dfs(int i,int fa){
    dep[i]=dep[fa]+1;
    f[i][0]=fa;
    for(register int j=1;j<18;++j){
        f[i][j]=f[f[i][j-1]][j-1];
    }
    for(register int j=e[i].head;j;j=e[j].Next){
        int v=e[j].ver;
        if(v==fa) continue;
        dfs(v,i);
    }
}

int lca(int u,int v){
    if(dep[u]=0;--i){
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    }
    if(u==v) return u;
    for(register int i=19;i>=0;--i){
        if(f[u][i]!=f[v][i]){
            u=f[u][i],v=f[v][i];
        }
    }
    return f[u][0];
}

int main(){
    scanf("%d%d%d",&n,&m,&root);
    for(register int i=1,u,v;i