lca模板题 70tps RE+TLE

#include<bits/stdc++.h>
using namespace std;
const int N=500001; 
int n,m,s,dep[N],f[N][21];
struct edge
{
	int to,next;
}e[N];
int head[N],tot;
void add(int u,int v)
{
	e[++tot]={v,head[u]};
	head[u]=tot;
}
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,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 main()
{
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<'\n';
	}
}