lca初学者,样例和一号点过了,实在查不出错误,求纠正
查看原帖
lca初学者,样例和一号点过了,实在查不出错误,求纠正
597716
IT__windy楼主2022/3/12 08:54
#include<bits/stdc++.h>
#define N 500010
using namespace std;
struct tree{
	int v,nex;
}e[N*2];
int f[N*2][30],head[N],lg[N],deep[N];
int tot;
long long ans;
void add(int x,int y){
	e[++tot].v=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
void dfs(int now,int fa){
	f[now][0]=fa;
	deep[now]=deep[fa]+1;
	for(int i=1;i<=lg[deep[now]];i++)
		f[now][i]=f[f[now][i-1]][i-1];
	for(int i=head[now];i;i=e[i].nex)
		if(e[i].v!=fa)
			dfs(e[i].v,now);
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	while(deep[x]>deep[y])
		x=f[x][lg[deep[x]-deep[y]]-1];	
	if(x==y)return x;
	for(int k=lg[deep[x]];k>=0;k--){
		if(f[x][k]!=f[y][k])
			x=f[x][k],y=f[x][k];
	}
	return f[x][0];
}
int main(){
	int n,m,x,y;
	int a,b,c;
	int t1,t2,t3,t;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	while(m--){
		ans=0;
		scanf("%d%d%d",&a,&b,&c);
		t1=lca(a,b);
		t2=lca(a,c);
		t3=lca(b,c);
		if(t1==t3)t=t2;
		else if(t1==t2)t=t3;
		else if(t2==t3)t=t1;
		ans=deep[a]+deep[b]+deep[c]-deep[t1]-deep[t2]-deep[t3];
		printf("%d %lld\n",t,ans);
	}
	return 0;
}
2022/3/12 08:54
加载中...