倍增求 $LCA$

发表于 | 更新于 | 阅读次数：

好久没有更新了，来写 $(shui)$ 一篇 $LCA$ 的博客。

以前觉得 $LCA$ $($最近公共祖先$)$是神仙学的东西， $fj$ 讲的时候我也贼吉尔懵逼，现在看来也没有那么难。

当我们想求 $LCA(x,y)$ 时，如果一格一格跳直到跳到同一位置，不知道会跳到哪一年去，于是我们用到了一个神奇的东西：倍增。

众所周知任何数都可以用二进制，所以我们可以每次跳 $2^i$ 步，大大加快效率。这里我们用 $fa[i][j]$ 代表第 $i$ 号节点往上跳 $2^j$ 步到达的位置。所以很容易推出来: $fa[i][j]=fa[fa[i][j-1]][j-1]$ 。

然后跳的具体过程看代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>

#define For(a,x,y) for(int a=x;a<=y;a++)
#define Bac(a,x,y) for(int a=x;a>=y;a--)

using namespace std;

const int N=5e5;
const int M=5e5;

int n,m,s;
int depth[N+5],fa[N+5][25];
int lg[N+5];

struct Edge{
	int to,next;
}edge[2*M+5];

int num_edge,head[N+5];

void add_edge(int from,int to)
{
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge;
}

int lca(int x,int y)
{
	if(depth[y]<depth[x])
		swap(x,y);
	while(depth[x]<depth[y])
		y=fa[y][lg[depth[y]-depth[x]]];//先跳到同一深度
	if(x==y)return x;
	Bac(i,lg[depth[x]],0)
	{
		if(fa[x][i]!=fa[y][i])//因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果相等就代表跳多了
			x=fa[x][i],y=fa[y][i];
	}
	return fa[x][0];
}

void dfs(int x,int fat)
{
	depth[x]=depth[fat]+1;
	fa[x][0]=fat;
	for(int i=1;(1<<i)<=depth[x];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int p=head[x];p;p=edge[p].next)
		if(edge[p].to!=fat)dfs(edge[p].to,x);
}

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	int u,v;
	For(i,1,n-1)
	{
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	lg[0]=-1;
	For(i,1,n)
		lg[i]=lg[i/2]+1;//优化，预处理log
	dfs(s,0);
	int a,b;
	For(i,1,m)
	{
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}