题解 - 【模板】最近公共祖先

Whisperain LV 5 @ 2021-10-6 20:41:44

本题的核心思路：倍增。如果暴力求LCA，要从两个节点开始，一步一步往根节点方向走，记录路径，再从路径最后（就是根节点）开始比较，比较什么时候后出现不同。代码如下：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=500000+5;

int head[MAXN];
int father[MAXN];
bool visited[MAXM];
int bianshu;

struct edge
{
	int v,next;
}g[2*MAXM];

void addedge(int u,int v)
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
}

queue <int> q;
int s;
void bfs()
{
	q.push(s);
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				q.push(g[i].v);
			}
		}
	}
	
}

int path1[MAXN];
int path2[MAXN];
int cntp1,cntp2;
int ans;
int main()
{
	int n,q;
	int uu,vv;
	int a,b;
	int LCA,a1,a2;
	scanf("%d%d%d",&n,&q,&s);
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}
	father[s]=s;
	visited[s]=true;
	bfs();
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d",&a,&b);
		for(int j=a;j!=s;j=father[j])
		{
			path1[++cntp1]=j;
		}
		path1[++cntp1]=s;
		for(int j=b;j!=s;j=father[j])
		{
			path2[++cntp2]=j;
		}
		path2[++cntp2]=s;
		while(path1[cntp1--]==path2[cntp2--])
		{
			ans=path1[cntp1+1];
		}
		printf("%d\n",ans);
		memset(path1,0,sizeof(path1));
		memset(path2,0,sizeof(path2));
		cntp1=0;
		cntp2=0;
		ans=0;
	}
	return 0;
}

然而，暴力的时间和空间复杂度根本无法接受。我们来思考下面这个问题：我为什么要一个一个跳到根节点呢？于是乎，“倍增”就出现了。定义jump[a][b]数组的意义如下：编号为a的点往根节点方向走(2^b)次之后的点的编号。每一次不需要一个一个往根节点方向走，而是采取了一种类似于跳跃的模式。往根节点方向走（2^0)次，即得到这个点的父亲节点。所以先初始化数组：

for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值

然后，再将jump[i][1] jump[i][2]等求出来。 jump[i][j]可以通过jump[i][j-1]再往根节点方向走j-1次得到。推得状态转移方程：jump[i][j]=jump[jump[i][j-1]][j-1];

for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组

接下来我们要开始求最近公共祖先了。然而，如果节点a深度为16，节点b深度为32，所求得的跳跃次数、路径长度都是不一样的，我们又要记录路径然后从后往前比较。于是乎，我们想了一个办法：先把a，b跳跃到同一深度，再进行剩下的跳跃。（有更简便写法）

if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
				}
			} 
		}//使得a,b位于同一深度

如果这个时候已经跳到同一个点，即a==b，则直接输出，否则进行我们最后的跳跃。只要jump[i][k]!=jump[j][k]（k取值可以不做限制，因为无意义的那些范围的jump值均会是0）我们就跳跃。跳跃完之后，你会惊奇的发现father[a]==father[b];（可以自己模拟一下）所以我们输出任意一边的father均可。一些没提到的细节和代码如下：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=500000+5;
const int MAXM=1000000+5;

int head[MAXN];//链式前向星 

int father[MAXN];//父亲节点 

bool visited[MAXN];

int bianshu;

struct edge//链式前向星 
{
	int v,next;
}g[2*MAXM];//双向边，记得开2倍范围 

void addedge(int u,int v)//链式前向星无权值加边 
{
	g[++bianshu].next=head[u];
	g[bianshu].v=v;
	head[u]=bianshu;
	return;
} 

queue <int> q;//bfs用
 
int dep[MAXN];//每个点的深度 

void bfs(int s,int depth)//求father 
{
	q.push(s);
	dep[s]=depth;
	while(!q.empty())
	{
		int ppp=q.front();
		q.pop();
		for(int i=head[ppp];i;i=g[i].next)//遍历 
		{
			if(!visited[g[i].v])
			{
				visited[g[i].v]=true;
				father[g[i].v]=ppp;
				dep[g[i].v]=dep[ppp]+1;//存储深度，比父亲节点深度大1 
				q.push(g[i].v);
			}
		}
	}
}

int jump[MAXN][35];//定义：j[a][b]为a号点往根节点方向走(1<<b)次后的节点编号 

int main()
{
	int n,q,s;
	int uu,vv;
	int a,b;
	int tmp;//深度差 
	
	scanf("%d%d",&n,&q);//有时候需要读入s 
	s=1; 
	
	for(int i=1;i<=n-1;++i)
	{
		scanf("%d%d",&uu,&vv);
		addedge(uu,vv);
		addedge(vv,uu);
	}//加边 
	
	father[s]=0;//注意：father[根]一定要设为0，否则后面跳跃时出问题 
	visited[s]=true;
	bfs(s,1);//求father数组 
	
	for(int i=1;i<=n;++i)
	{
		jump[i][0]=father[i];
	}//jump初值 
	for(int j=1;j<=30;++j)
	{
		for(int i=1;i<=n;++i)
		{
			jump[i][j]=jump[jump[i][j-1]][j-1];
		}
	}//初始化jump数组 
	 
	while(q--)//操作 
	{
		scanf("%d%d",&a,&b);
		
		tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);//深度差值 
		
		if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					a=jump[a][k];
					tmp-=(1<<k);
				}
			} 
		}
		else if(dep[b]>dep[a]) 
		{
			for(int k=30;k>=0;--k)
			{
				if(tmp>=(1<<k))
				{
					b=jump[b][k];
					tmp-=(1<<k);
				}
			} 
		}//使得a,b位于同一深度 
		
		if(a==b)//跳到同一个点，即LCA就是当前的点，需要特判。 
		{
			printf("%d\n",a);
			continue;
		}
		for(int k=30;k>=0;--k)
		{
			if((jump[a][k]^jump[b][k]))//异或符号^在此处等价于！= 符号 
			{
				a=jump[a][k];
				b=jump[b][k];
			}
		}//跳2的k次方次
		 
		printf("%d\n",father[a]);
	}
	return 0;
}

感谢阅读我这一篇又臭又长的题解。

Whisperain @ 2021-10-15 20:59:27

好像有一句写错了求jump[i][1] jump[i][2]的时候 jump[i][j]是要通过jump[i][j-1]再往根节点方向走 $2^（j-1）$ 次得到
Whisperain @ 2021-10-15 21:00:08

就是说2的j-1次方次
王靖翔 @ 2023-10-17 20:07:21

%%%