LCA 求条样例不过仿照oi wiki
查看原帖
LCA 求条样例不过仿照oi wiki
734379
Shadow_T楼主2024/8/27 21:26
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int fa[maxn][33];
int dep[maxn];
int dis[maxn][33];
#define pii pair<int,int>
#define fir first
#define sec second
#define pb push_back
vector<pii> g[maxn];
void Ios()
{
	ios::sync_with_stdio (0);
	cin.tie(0);
	cout.tie(0);
}
void dfs(int x,int y)
{
	fa[x][0]=y;
	dep[x]=dep[fa[x][0]]+1;//dep[x]=dep[y]+1;
	for(int i=1;i<31;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
		dis[x][i]=dis[fa[x][i-1]][i-1]+dis[x][i-1];
	}
	for(int i=0;i<g[x].size();i++)
	if(g[x][i].fir!=y)
	{
		dis[g[x][i].fir][0]=g[x][i].sec;
		dfs(g[x][i].fir,x);
	} 
}
int lca(int x,int y)
{
	if(dep[x]>dep[y]) swap(x,y);
	int t=dep[y]-dep[x],ans=0;
	for(int i=0;t>0;i++,t/=2)
	if(t&1) ans+=dis[y][i],y=fa[y][i];
	if(x==y) return ans;
	for(int i=30;i>=0;i--)
	{
		if(y==x) break;
		if(fa[x][i]!=fa[y][i])
		{
			ans+=dis[x][i]+dis[y][i];
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	ans+=dis[x][0]+dis[y][0];
	return ans;
}
signed main()
{
	Ios();
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		g[y].pb({x,1});
		g[x].pb({y,1});
	}
	dfs(s,0);
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<"\n";
	}
	return 0;
}
2024/8/27 21:26
加载中...