求调LCA模板

#include<iostream> 
#include<cstring>
using namespace std;
const int N=5e5+10;
int n,m,s,f[N][30],dep[N],log[N];
int to[N],h[N],ne[N],idx;
bool vst[N]={false};

void add(int u,int v)
{
	to[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}

void dfs(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=to[i];
		if(vst[v]) continue;
		vst[v]=true;
		f[v][0]=u;
		dep[v]=dep[u]+1;
		for(int j=1;j<=log[dep[v]];j++)
		{
			f[v][j]=f[f[v][j-1]][j-1];	
		}	
		dfs(v);
	}	
}

int LCA(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=log[dep[x]];i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i]; 
	}
	if(x==y) return x;
	for(int i=log[dep[x]];i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int main()
{
	log[0]=0;
	memset(h,-1,sizeof h);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y),add(y,x);
		log[i]=log[i/2]+1;
	}
	dfs(s);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		cout<<LCA(a,b)<<" ";
	}
	return 0; 
}