LCA：倍增最近公共祖先

算法理解

fa[u][i] 表示节点 u 的第 2^i 个祖先。查询时先把较深节点跳到相同深度；如果两点还不同，就从最大的 i 同时向上跳，直到它们的父亲相同。

• 复杂度：预处理 O(n log n)，单次查询 O(log n)。
• 注意：LOG 必须覆盖最大深度；深链上递归 DFS 可能爆栈，原模板提供的 BFS 预处理更稳。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
#define endl '\n'
using pii=pair<int,int>;
const int mod=1e9+7;
const int maxn=500000+7;
#define lowbit(x) (x&(-x))
#define vc vector<int>

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,m,s;
int d[maxn];  //深度
int f[maxn][21];  //倍增祖先数组
vector<int>g[maxn];

//BFS预处理深度与f[u][0]
void bfs(int root)
{
	queue<int>q;
	q.push(root);
	f[root][0]=0;
	d[root]=1;

	while (q.size())
	{
		int u=q.front();
		q.pop();

		for (int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if (v!=f[u][0])
			{
				f[v][0]=u;
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	//迭代预处理所有倍增层f[u][i]
	for (int i=1;i<=20;i++)
	{
		for (int u=1;u<=n;u++)
		{
			f[u][i]=f[f[u][i-1]][i-1];
		}
	}

}

void dfs(int u,int fa)
{
	f[u][0]=fa;
	d[u]=d[fa]+1;

	for (int i=1;(1<<i)<=d[u];i++)
	{
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for (auto v:g[u])
	{
		if (v!=fa)
		{
			dfs(v,u);
		}
	}
}

int lca(int x,int y)
{
	//让y为更深的点
	if (d[x]>d[y])
	{
		swap(x,y);
	}
	//拉平深度
	for (int i=20;i>=0;i--)
	{
		if (d[x]<=d[y]-(1<<i))
		{
			y=f[y][i];
		}
	}
	if (x==y) return x;

	for (int i=20;i>=0;i--)
	{
		if (f[x][i]==f[y][i]) continue;
		else 
		{
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}

//树上两点距离公式
inline int getdis(int x,int y)
{
	int anc = lca(x,y);
	return d[x] + d[y] - 2*d[anc];
}

void solve()
{
	cin>>n>>m>>s;
	for (int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
//	dfs(s,0);
	bfs(s);
	for (int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}