倍增LCA

倍增LCA

#include<bits/stdc++.h>
#define maxn 100005

using namespace std;

int n,m,s,t;
int dep[maxn],head[maxn],f[maxn][20];

struct node
{
	int to;
	int next;
}e[maxn];

inline void add(int u,int v)
{
	++t;
	e[t].to = v;
	e[t].next = head[u];
	head[u] = t;
}

inline 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];
}

inline void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	for(int i=1;(1<<i)<=dep[u];i++)
	{
	    f[u][i] = f[f[u][i-1]][i-1];
	}
	for(int i=head[u];i>0;i=e[i].next)
	{
		int v = e[i].to;
		if(v==fa) continue;
		f[v][0] = u;
		dfs(v,u);
	}
}

int main()
{
    cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
	    int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
	    int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}