526互联

最近公共祖先(LCA)

发布时间 2023-07-11 12:02:44作者: xxcdsg

最近公共祖先(LCA)

主要思路：一个节点的\(2^n\)的祖先是那个节点\(2^{n-1}\)的祖先的\(2^{n-1}\)的祖先

也就是说\(f[x][n]=f[f[x][n-1]][n-1]\)

还要计算\(log_2\)的值，记录深度

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 10;

int fa[MAXN][30],lg[MAXN],dp[MAXN];

vector<int> ve[MAXN];//记录连接

void dfs(int son,int dad)
{
	fa[son][0] = dad;//第一个祖先
	dp[son] = dp[dad] + 1;
	for(int i = 1;i <= 29;i++) fa[son][i] = fa[fa[son][i - 1]][i - 1];
	int end = ve[son].size();
	for(int i = 0;i < end;i++)
		if(ve[son][i] != dad)
			dfs(ve[son][i],son);
}

void flg(int n) {
	for(int i = 1;i <= n;i++) lg[i] = lg[i - 1] + (i == (2 << lg[i - 1]));
}

int find(int x,int y)
{
	if(dp[x] < dp[y])
		swap(x,y);
	while(dp[x] != dp[y]) x = fa[x][lg[dp[x]-dp[y]]];
	if(x == y) return x;
	for(int i = 29;i >= 0;i--) if(fa[x][i] != fa[y][i]) {x = fa[x][i],y = fa[y][i];}
	return fa[x][0];
}

int main()
{
	ios::sync_with_stdio(false);//写了using namespace std;
	int n,m,s;cin >> n >> m >> s;
	flg(n);
	for(int i = 1;i <= n - 1;i++)
	{
		int x,y;cin >> x >> y;
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	dfs(s,s);
	for(int i = 1;i <= m;i++)
	{
		int x,y;cin >> x >> y;
		cout << find(x,y) << endl;
	}
}