【算法】最近公共祖先(lca)——倍增，tarjan_最近公共祖先 图 倍增

问题引入

给定一棵包含 n 个节点的有根无向树，节点编号互不相同，
有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。
用并查集吗？可以，但时间复杂度太高了，很容易TLE，所以我们用LCA。

介绍

最近公共祖先是什么意思呢？其实就是对于两个点x和y，如果点t满足既是x的祖先又是y的祖先，同时是离它们最近的共同的祖先，那么t就是x，y的最近公共祖先。
如图：

a是b，c的最近公共祖先，a是p，q的最近公共祖先。

lca就是用来求两点的最近公共祖先的算法。

倍增(在线算法)

原理

类似二分，用二进制数求出两点间的lca
分两种情况：
1.两点在同一棵子树上：
如一个链表 a-b-c，其中a为根节点，求lca(a,c)
很容易得出lca(a,c)=a

2.两点不在同一棵子树上：
首先，将两点弄到同一个高度。
接着，两点同时往上跳同一高度，跳到极限（再往上一格就撞在一起）
最后，极限+1就是lca了
如图：
求lca(g,f)
先弄到同一高度（蓝色箭头）
然后一起跳（红色箭头）
最后跳到极限，所以lca(g,f)=a

代码实现

存边

我们用邻接表存边：

struct Edge
{
	int next,t;	
}edge[N];
inline void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
1
2
3
4
5
6
7
8

需要前置知识：邻接表

初始化

想要实现这个算法，首先我们要记录各个点的深度和它跳2^i步后的节点
我们用数组d表示每个节点的深度，f[i][j]表示节点i 跳2^j步后的节点位置
所以初始化如下：

void dfs(int u,int fa)//u表示当前节点，fa表示它的父亲节点
{
	f[u][0]=fa,d[u]=d[fa]+1;
	for(int i=1;i<=lg[d[u]];i++)//非常关键
		f[u][i]=f[f[u][i-1]][i-1];//意思是u的2^i祖先等于u的2^(i-1)祖先的2^(i-1)祖先
								  //因为2^i = 2^(i-1) + 2^(i-1)
	for(int i=head[u];i;i=edge[i].next)//便利u的所有相连节点
		if(edge[i].t!=fa)//如果不是父亲节点
			dfs(edge[i].t,u);//继续搜索
}
for(int i=1;i<=n;i++)//预先算出log_2(i)+1的值，用的时候直接调用就可以了
	lg[i]=lg[i-1]+(1<<lg[i-1]==i);//看不懂的可以手推一下
dfs(s,0);//s为根节点
1
2
3
4
5
6
7
8
9
10
11
12
13

LCA

I.深度调换

我们求lca(x,y)，默认x比y要深，所以如果x没y深，将x,y交换一下：

if(d[x]<d[y])
	swap(x,y);//注意 交换x和y，不是d[x]和d[y]
1
2

II.调至同一深度

我们已经让x的深度比y大了，现在将它们调至同一深度：

while(d[x]>d[y])
	x=f[x][lg[d[x]-d[y]]-1];//手动推一下，每次都跳到准极限
1
2

III.特殊情况

现在x和y在同一深度，如果x==y，那么x就是lca(x,y)的值：

if(x==y)
	return x;
1
2

IV.一起跳

现x和y在同一深度的不同子树上，我们让它们一起跳2^i步，直到极限（上文说过）：

for(int i=lg[d[x]]-1;i>=0;i--)
	if(f[x][i]!=f[y][i])//如果跳了之后不相等，就跳
		x=f[x][i],y=f[y][i];
1
2
3

V.返回

此时x和y都跳到了极限，所以极限+1为所求：

return f[x][0];
1

VI.例子

int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	while(d[x]>d[y])
		x=f[x][lg[d[x]-d[y]]-1];
	if(x==y)
		return x;
	for(int i=lg[d[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

例题

题目

祖孙询问
给定一棵包含 n 个节点的有根无向树，节点编号互不相同，
有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式
输入第一行包括一个整数 表示节点个数；
接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根；
第 n+2 行是一个整数 m 表示询问个数；
接下来 m 行，每行两个不同的正整数 x 和 y，表示一个询问。
1≤n,m≤4×104,
1≤每个节点的编号≤4×104

输出格式
对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

输入/输出例子1
输入：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出：

1
0
0
0
2
样例解释
无

code

#include<bits/stdc++.h>
using namespace std;
struct fy
{
	int t,next;
}edge[1000001];
int head[1000001],cnt,x,y,n,m,s,d[1000001],f[1000001][22],lg[1000001];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
void dfs(int u,int fa)
{
	f[u][0]=fa,d[u]=d[fa]+1;
	for(int i=1;i<=lg[d[u]];i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].next)
		if(edge[i].t!=fa)
			dfs(edge[i].t,u);
}
int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	while(d[x]>d[y])
		x=f[x][lg[d[x]-d[y]]-1];
	if(x==y)
		return x;
	for(int i=lg[d[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(y!=-1)
			add(x,y),add(y,x);
		else
			s=x;
	}
	scanf("%d",&m);
	for(int i=1;i<=n;i++)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		int z=lca(x,y);
		if(z==x)
			printf("1\n");
		else if(z==y)
			printf("2\n");
		else
			printf("0\n");
	}
	return 0;
}
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

总结

类似二分，O(nlogn)

Tarjan(离线算法)

原理

类似dfs，先搜一块子树，根据已知条件求答案
区别倍增：先搜集完答案信息再dfs，不是拿一个问题得出一个答案
方法：并查集

代码实现

初始化

存边

struct fy
{
	int next,t;	
}edge[N];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
1
2
3
4
5
6
7
8

并查集

int ga(int x)
{
	if(x!=fa[x])
		fa[x]=ga(fa[x]);
	return fa[x];
}
for(int i=1;i<=n;i++)
	fa[i]=i;//并查集初始化
1
2
3
4
5
6
7
8

Tarjan

I.标记+枚举子节点

	vis[u]=1;//标记已经搜过
	for(int i=head[u];i;i=edge[i].next)//枚举全部子节点
	{
		int j=edge[i].t;
		if(!vis[j])//判断标记
			tarjan(j),fa[j]=u;
	}
1
2
3
4
5
6
7

II.查找答案

	for(int i=0;i<a[u].size();i++)//查找问了关于u的问题
	{
		int y=a[u][i].u,id=a[u][i].v;
		if(vis[u])//如果找过了
			b[id]=ga(y);//直接得答案
	}
1
2
3
4
5
6

例题

题目

最近公共祖先
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先

输入格式
第一行包含三个正整数 N,M,S, 分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1 行每行包含两个正整数 x, y ，表示 x 结点和 y 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 M 行每行包含两个正整数 a, b ，表示询问 a 结点和 b 结点的最近公共祖先。 1<=N,M<=500000

输出格式
输出包含 M 行，每行包含一个正整数，依次为每一个询问的结果。

输入/输出例子1
输入：

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出：

4
4
1
4
4

样例解释

无

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
struct fy
{
	int next,t;	
}edge[N];
struct ff
{
	int u,v;
};
int head[N],cnt,fa[N],n,m,s,b[N],vis[N],x,y;
vector<ff>a[N];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
int ga(int x)
{
	if(x!=fa[x])
		fa[x]=ga(fa[x]);
	return fa[x];
}
void tarjan(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int j=edge[i].t;
		if(!vis[j])
			tarjan(j),fa[j]=u;
	}
	for(int i=0;i<a[u].size();i++)
	{
		int y=a[u][i].u,id=a[u][i].v;
		if(vis[u])b[id]=ga(y);
	}
}
signed main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
		scanf("%d%d",&x,&y),add(x,y),add(y,x);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x,&y),a[x].push_back({y,i}),a[y].push_back({x,i});
	for(int i=1;i<=n;i++)
		fa[i]=i;
	tarjan(s);
	for(int i=1;i<=m;i++)
		printf("%d\n",b[i]);
} 
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

总结

类dfs，常数优化，不过尽量打倍增

总结

很好的一个树形结构的算法，蒟蒻可以去这里刷题：lca刷题处