倍增LCA20pts求调
查看原帖
倍增LCA20pts求调
524085
yanbinmu楼主2023/5/12 21:10
#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int n,m,x,y,z,a,b,c;
int head[N],tot = 1;
int f[N][21],dep[N];
struct node{
	int to,nxt,w;
}edge[N];
void add(int u,int v,int w){
	edge[tot].w = w;
	edge[tot].to = v;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}
void init(int u,int fa){
	dep[u] = dep[fa]+1;
	f[u][0] = fa;
	for(int i = 0;i<20;i++){
		f[u][i+1] = f[f[u][i]][i];
	}
	for(int i = head[u];i;i=edge[i].nxt){
		int to = edge[i].to;
		if(to==fa)continue;
		f[to][0] = u;
		init(to,u);
	}
}
int LCA(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(int i = 20;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y)return x;
	}
	for(int i = 20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int pos;
int dist(int x,int y){
    pos=LCA(x,y);
    return dep[x]+dep[y]-2*dep[pos];
}
int que(int a,int b,int c,int end){
    return (dist(a,end)+dist(b,end)+dist(c,end));
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i<n;i++){
		scanf("%d %d",&x,&y);
		add(x,y,1);
//		add(y,z,1);
	}
	init(1,0);
	for(int i = 1;i<=m;i++){
		scanf("%d %d %d",&a,&b,&c);
		int A=LCA(a,b);
        int B=LCA(b,c);
        int C=LCA(a,c);
        if(A==B) printf("%d %d\n",C,que(a,b,c,C));
        else if(B==C) printf("%d %d\n",A,que(a,b,c,A));
        else if(C==A) printf("%d %d\n",B,que(a,b,c,B));
		
	}
	return 0;
}
2023/5/12 21:10
加载中...