求助
查看原帖
求助
422191
ulrica_AKall楼主2021/3/7 16:27

此代码究竟哪里出问题了???

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,root;
int ee,h[500005],nex[500005<<1],to[500005<<1];
int fa[500005][20],dep[500005];
void addedge(int x,int y)
{
	nex[++ee]=h[x];
	to[ee]=y;
	h[x]=ee;
}
void dfs(int x,int pre)
{
	dep[x]=dep[pre]+1;
	fa[x][0]=pre;
	for(int i=h[x];i;i=nex[i])
	if(to[i]!=pre)
	dfs(to[i],x);
}

int getlca(int x,int y)
{
	if(dep[x]<dep[y])
	swap(x,y);
	while(dep[x]>dep[y])
	x=fa[x][(int)log2(dep[x]-dep[y])];
	if(x==y)
	return y;
	for(int j=20;j>=0;j--)
	if(fa[x][j]!=fa[y][j])
	x=fa[x][j],y=fa[y][j];
	return fa[x][0];
}
signed main()
{
	cin>>n>>q>>root;
	for(int i=1,x,y;i<n&&cin>>x>>y;i++)
	addedge(x,y),addedge(y,x);
	dfs(root,0);
	for(int j=1;j<=20;j++)
	for(int i=1;i<=n;i++)
	fa[i][j]=fa[fa[i][j-1]][j-1];
	while(q--)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",getlca(x,y));
	}
	return 0;
}
2021/3/7 16:27
加载中...