【洛谷P3379】【模板】最近公共祖先(LCA)

发布于 2022-05-25  1314 次阅读


题目链接:P3379 【模板】最近公共祖先(LCA) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

LCA是什么?

LCA(Lowest Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

求解LCA的方法

朴素法,复杂度O(N):先把两个点x和y跳到同一深度,然后同时往上跑,当x == y时返回x或y。当整棵树接近一条链状时,复杂度达到O(N)。

LCA倍增法,复杂度O(logN),这也是我们要写的方法。

首先要预处理出每个点的所有祖先。可以用二进制分解,logN来算出。

倍增法利用了二进制的性质,每一个非负整数都可以由二进制表示出来,那么我们fa[x][i]表示x向上跳了2 ^ i个格子之后所在的位置。

不难发现fa[x][0]就是x的父节点(向上走2^0格),而fa[x][i] = fa[fa[x][i - 1]][i - 1],也就是说x向上走2 ^ i格 = 向上走2 ^ (i - 1),再走2 ^ (i - 1),这里用到了动态规划的思想,因为在dfs递归到x时,x的父亲的fa是处理完了的。

处理完fa之后,我们就要求x和y的LCA了。

由朴素法提供的思路,我们先把x和y移动到同一深度。

设x的深度大于y(如果x深度小于y深度就交换x,y),从大到小(有点贪心的意思)遍历x的所有二进制位(假设为20位,基本够用),如果x向上移动后深度依然大于等于y就可以移动。最后一定能保证dep[x] == dep[y]。

举个例子,一开始dep[x] = 15, dep[y] = 2。x就向上走8 + 4 + 1步可以到y的深度。

当xy深度相同时,如果x==y就直接返回x或y。否则继续同时向上跑,如果x的2^i祖先和y的2^i祖先相等的话说明跑多了,如果不相等,说明还没到LCA,就可以往上跑,跑完之后可以保证x y一定位于LCA的下一层,那么LCA就是fa[x][0]或fa[y][0]。

完毕。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 10;
int N, M, S, T = 20;
int fa[maxn][25], dep[maxn];

vector<int> g[maxn];

void dfs(int x,int pre)
{
	dep[x] = dep[pre] + 1;
	fa[x][0] = pre;
	for(int i = 1;i <= T; ++ i)fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(auto &i : g[x])
	{
		if(i == pre)continue;
		dfs(i, x);
	}
}

int LCA(int x,int y)
{
	if(dep[x] < dep[y])swap(x, y);
	for(int i = T;i >= 0; -- i)if(dep[fa[x][i]] >= dep[y])x = fa[x][i];
	if(x == y)return x;
	for(int i = T;i >= 0; -- i)if(fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i];
	return fa[x][0];
} 

signed main()
{
	scanf("%lld %lld %lld", &N, &M, &S);
	for(int i = 1;i < N; ++ i)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		g[x].push_back(y);g[y].push_back(x);
	}
	dep[0] = -1;
	dfs(S, 0);//构造树 
	while(M --)
	{
		int x, y;scanf("%lld %lld", &x, &y);
		printf("%lld\n", LCA(x, y));
	}
	return 0;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09