倍增求 $lca$ 的方法主要有两个步骤：

$1.$ 把 $x$ 和 $y$ 提到相同深度。

$2.$ $x$ 和 $y$ 同步跳，跳到 $lca$。

步骤 $1$

先求出 $d_x$ 和 $d_y$，这时只需要在 $dfs$ 中就可以完成：$d_u = d_{father} + 1$

定义 $fa_{u,i}$ 表示 $u$ 节点的第 $2^i$ 个祖先，有一个非常巧妙的递推关系：

意思是从 $u$ 节点先跳到 $u$ 的第 $2^{i-1}$ 个祖先，再从 $2^{i-1}$ 个祖先跳到 $2^{i}$ 个祖先。

简单来说，就是 $2^i=2^{i-1}\times 2^{i-1}$。

在此要特判一下 $x==y$，有可能 $lca(x,y)=x$，这种情况下 $x$ 为 $y$ 的祖先。

步骤$2$

每一次跳 $2^{i}$，直到跳到 $lca(x,y)$ 为止。

有两种情况：

• $fa_{x,i}=fa_{y,i}$，这是一个公共祖先，但不是 $lca$，说明跳过头了，回去换一个更小的跳。

• $fa_{x,i}≠fa_{y,i}$，说明还没跳到公共祖先，那么更新 $x=fa_{x,i},y=fa_{y,i}$。

最后 $fa_{x,0}$ 就是 $lca(x,y)$。

#include <iostream>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define dow(i, j, k) for(int i = j; i >= k; i--)
using namespace std;//命名空间
const int N = 5e5 + 5;
int n, m, s, fa[N][25], d[N]; 
vector<int> g[N];
inline void dfs(int u, int fat)
{
	d[u] = d[fat] + 1;//计算深度 
	fa[u][0] = fat;//初始化，u的父节点为fat 
	for(int i = 1; (1 << i) <= d[u]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];//初始化，最多跳到根节点	
	for(int i = 0; i < (int)g[u].size(); i++){
		int v = g[u][i];
		if(v == fat) continue;
		dfs(v, u);//向下搜索 
	}
}
inline int lca(int x, int y)//lca的部分 
{
	if(d[x] < d[y]) swap(x, y);//让x的深度更大 
	dow(i, 20, 0)
		if(d[x] - (1 << i) >= d[y]) x = fa[x][i];
	if(x == y) return x;//lca(x,y)=x，直接返回 
	dow(i, 20, 0)
		if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];//向上跳 
	return fa[x][0];//最终的lca 
}
int main()//主函数
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s;
	for(int i = 1; i < n; i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);	
	}
	dfs(s, 0);
	while(m--){
		int x, y;
		cin >> x >> y;
		int z = lca(x, y);
		cout << z << "\n";
	}
	return 0;//华丽结束
}