123456倍

用户名：h1910819075

访问量：2638

签　名：

AC 总在意料之外

等　　级
排　　名	148
经　　验	7290
参赛次数	6
文章发表	6
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高-秘密行动题解
浏览：191

蓝桥杯2019年第十届真题-修改数组题解
浏览：165

题解 2302: 蓝桥杯2019年第十届真题-糖果
浏览：284

你可能喜欢

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

[2018年第九届真题]版本分支最近公共祖先的模板题

　　作者: 123456倍　　　　发表时间：2021-05-08 22:15:22 浏览：188　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-版本分支

**   最近公共祖先模板题，找出现这个两个最近公共祖先，判断这个祖先是否和a一样，一样就是yes，否则是no；**

代码：
```
#include<bits/stdc++.h>
using namespace std;
const int N= 1e6+10;
vector<int> e[N];
int lg[N],fa[N][22],dis[N];
int n,m;

inline void dfs(int x,int fath)
{
	fa[x][0]=fath;
	dis[x]=dis[fath]+1;
	
	for(int i=1;i<=lg[dis[x]];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=fath)
			dfs(e[x][i],x);
	}
}

inline int LCA(int x,int y)
{
	if(dis[x]<dis[y])
		swap(x,y);
	
	while(dis[x]>dis[y])
		x=fa[x][lg[dis[x]-dis[y]]-1];
	
	if(x==y) return x;
	
	for(int k=lg[dis[x]]-1;k>=0;k--)
		if(fa[x][k]!=fa[y][k])
			x=fa[x][k],y=fa[y][k];
	
	return fa[x][0];
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		int c=LCA(a,b);
		if(c==a)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

123456倍

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

【计算球体积】（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

[2018年第九届真题]版本分支最近公共祖先的模板题

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

WU-链表数据求和操作（C++代码）

Wu-求圆的面积（C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

Tom数（C语言代码）

一元一次方程（C语言代码）

淘淘的名单（C语言代码）

剔除相关数（C语言代码）

整数分类问题为什么输出总是数字8啊

123456倍

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

【计算球体积】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

[2018年第九届真题]版本分支 最近公共祖先的模板题

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

WU-链表数据求和操作 （C++代码）

Wu-求圆的面积 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单的a+b （C语言代码）

Tom数 （C语言代码）

一元一次方程 （C语言代码）

淘淘的名单 （C语言代码）

剔除相关数 （C语言代码）

整数分类问题 为什么输出总是数字8啊

弟弟的作业（C语言代码）

【计算球体积】（C语言代码）

[2018年第九届真题]版本分支最近公共祖先的模板题

　　评论区

WU-链表数据求和操作（C++代码）

Wu-求圆的面积（C++代码）

Tom数（C语言代码）

一元一次方程（C语言代码）

淘淘的名单（C语言代码）

剔除相关数（C语言代码）

整数分类问题为什么输出总是数字8啊