ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年5月25日 1182点热度 1人点赞 3条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP lca 洛谷 算法竞赛 贪心
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

  • 嫩爹

    看了哥哥的文章,打比赛爆WA了 ( doge )

    2022年7月27日
    回复
    • Eriktse

      @嫩爹 好

      2022年7月27日
      回复
    • Eriktse

      @嫩爹 mua

      2022年9月5日
      回复
  • 取消回复

    Eriktse

    18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

    文章目录
    • LCA是什么?
    • 求解LCA的方法
    • 代码

    友情链接 | 站点地图

    COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

    Theme Kratos | Hosted In TENCENT CLOUD

    赣ICP备2022001555号-1

    赣公网安备 36092402000057号