请选择 进入手机版 | 继续访问电脑版

php中文网 | cnphp.com

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 82|回复: 0

C++ 实现最近公共祖先

[复制链接]

2112

主题

2119

帖子

7704

积分

管理员

Rank: 9Rank: 9Rank: 9

UID
1
威望
0
积分
5470
贡献
0
注册时间
2021-4-14
最后登录
2022-12-2
在线时间
522 小时
QQ
发表于 2022-10-2 20:33:07 | 显示全部楼层 |阅读模式
[C++] 纯文本查看 复制代码
#include<bits/stdc++.h>
using namespace std;
const int mxN(5e5),mxLg(19);
int n,q,rt,fa[mxLg+1][mxN+5],dep[mxN+5];
vector<int>nd[mxN+5];
void add(int u,int v){nd[u].push_back(v);}
void dfs(int u,int pr){
	fa[0][u]=pr,dep[u]=dep[pr]+1;
	for(int i(1);i<=mxLg;++i)fa[i][u]=fa[i-1][fa[i-1][u]];
	for(int i(0);i<nd[u].size();++i)if(nd[u][i]!=pr)dfs(nd[u][i],u);
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i(mxLg);i>=0;--i){
		if(dep[fa[i][u]]>=dep[v])u=fa[i][u];//如果要更新答案,要先更新再跳.
		if(u==v)return u;
	}
	for(int i(mxLg);i>=0;--i)if(fa[i][u]!=fa[i][v])u=fa[i][u],v=fa[i][v];//等于0也是相同的.
	return fa[0][u];//不是u.
}
int main(){
	scanf("%d%d%d",&n,&q,&rt);
	for(int i(1),u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(rt,0);int u,v;
	while(q--)scanf("%d%d",&u,&v),printf("%d\n",LCA(u,v));
	return 0;
}





上一篇:AC 自动机(C++ 实现)
下一篇:C++:多元一次方程组的解法
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

php中文网 | cnphp.com ( 赣ICP备2021002321号-2 )51LA统计

GMT+8, 2022-12-2 11:44 , Processed in 0.350652 second(s), 29 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

申明:本站所有资源皆搜集自网络,相关版权归版权持有人所有,如有侵权,请电邮(fiorkn@foxmail.com)告之,本站会尽快删除。

快速回复 返回顶部 返回列表