最近公共祖先(倍增,tarjan,树链剖分)

两个点的最近公共祖先，即两个点的所有公共祖先中，离根节点最远的一个节点。

倍增算法

1.dfs一遍，创建ST表

2.利用ST表求LCA


内容来源 D09 倍增算法 P3379【模板】最近公共祖先（LCA）

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 500000
int n,m,s;
vector<int>e[MAX_N+5];
int dep[MAX_N+5];
int fa[MAX_N+5][20];
void dfs(int now,int father)
{
	dep[now]=dep[father]+1;
	fa[now][0]=father;
	//向上跳1，2，4...步的祖先节点 
	for(int i=1;i<=19;i++)
	fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int v:e[now])
	{
		if(v==father)continue;
		dfs(v,now);
	}
	return ;
}
int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	//先跳到同一层 
	for(int i=19;i>=0;i--)
	if(dep[fa[u][i]]>=dep[v])
	u=fa[u][i];
	if(u==v)return u;
	//再跳到lca的下一层 
	for(int i=19;i>=0;i--)
	if(fa[u][i]!=fa[v][i])
	u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1,a,b;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(s,0);
	for(int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
} 

Tarjan算法

内容来源 D10 Tarjan算法 P3379【模板】最近公共祖先（LCA）

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 500000
int n,m,s;
vector<int>e[MAX_N+5];
vector<pair<int,int>>query[MAX_N+5];
int fa[MAX_N+5];
int vis[MAX_N+5];
int ans[MAX_N+5];
int find(int x)
{
	return fa[x]=(fa[x]==x?x:find(fa[x]));
}
void tarjan(int u)
{
	vis[u]=1;//入u时，标记u 
	for(auto v:e[u])
	{
		if(vis[v])continue;
		tarjan(v);
		fa[v]=u;//回u时，v指向u 
	}
	for(auto q:query[u])//离u时，枚举lca 
	{
		int v=q.first,t=q.second;
		if(vis[v])ans[t]=find(v);
	}
	return ;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1,a,b;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		query[a].push_back({b,i});
		query[b].push_back({a,i});
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	tarjan(s);
	for(int i=1;i<=m;i++)
	printf("%d\n",ans[i]);
	return 0;
} 

树链剖分算法

内容来源 D11 树链剖分 P3379【模板】最近公共祖先（LCA）

#include<iostream>
#include<vector>
using namespace std;
#define MAX_N 500000
int n,m,s;
vector<int>e[MAX_N+5];
int fa[MAX_N+5],sz[MAX_N+5],son[MAX_N+5],dep[MAX_N+5];
int top[MAX_N+5];
void dfs1(int u,int father)//搞fa,son,dep 
{
	fa[u]=father;dep[u]=dep[father]+1;sz[u]=1;
	for(int v:e[u])
	{
		if(v==father)continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])son[u]=v;
	}
	return ;
}
void dfs2(int u,int t)//搞top 
{
	top[u]=t;//记录链头 
	if(!son[u])return ;//无重儿子 
	dfs2(son[u],t);//搜重儿子 
	for(int v:e[u])
	{
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);//搜轻儿子 
	}
	return ;
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1,a,b;i<=n-1;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(s,0);
	dfs2(s,s);
	for(int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
} 

总结