RE70分
查看原帖
RE70分
243263
夜阑楼主2022/3/22 23:00

是不是哪里数组开小了???

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,next;};
node bian[500010];
int head[500010];
int n,m,s,cnt;
int lg[500010];
int fa[500010][1010]; 
int dep[500010];
void add(int x,int y){
	cnt++;
	bian[cnt].x=x;
	bian[cnt].y=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
} 
void dfs(int x,int rt){
	fa[x][0]=rt;
	dep[x]=dep[rt]+1;
	for(int i=1;i<=lg[dep[x]];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head[x];i;i=bian[i].next)
		if(bian[i].y!=rt)
			dfs(bian[i].y,x);
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
		x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y)return y;
	for(int i=lg[dep[x]]-1;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
void inke(){
	for(int i=1;i<=n;i++){
		head[i]=-1;
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
}
int main(){
	cin>>n>>m>>s;
	inke(); 
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);add(y,x);
	} 
	dfs(s,0);
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}
2022/3/22 23:00
加载中...