其实就是把x和y提到同一高度这一步骤我改了改，但我认为没有问题

假设x < y,我们用一个变量存一下x和y的深度之差

d = dep[y] - dep[x];

所以x要跳到它的第d个祖先，然后我们把d转为二进制

发现我们可以通过二进制表示出它的二次幂相加，例如

d = 27 -> 11011(二进制) -> 16 + 8 + 2 + 1 不难发现它的路径是确定的

我们只需要判断二进制每一位是否为1，为1的话就跳到第 2 ^ (二进制位数) 个祖先，这样从小到大跳和从大到小跳难道不一样吗？

本蒟蒻不明白为什么，求巨佬帮忙解惑

#include <bits/stdc++.h>
using namespace std;
vector <int> g[500100];
int n,m,s;
int f[500010][100],dep[500010];
void dfs(int u,int fa){
	f[u][0] = fa;
	dep[u] = dep[fa] + 1;
	for(auto v : g[u]){
		if(v == fa) continue;
		dfs(v,u);
	}
}
void init(){
	for(int j = 1;(1 << j) <= n;j++){
		for(int i = 1;i <= n;i++){
			f[i][j] = f[f[i][j-1]][j-1];
		}
	}
}
int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	int d = dep[u] - dep[v];
	for(int i = 0;i <= __lg(d);i++){//看这一行，我把循环反过来写了
		if(d >> i & 1){//位运算，二进制第i位的数
			u = f[u][i];
		}
	}
	if(u == v) return u;
	for(int i = 21;i >= 0;i--){
		if(f[u][i] != f[v][i]){
			u = f[u][i],v = f[v][i];
		}
	}
	return f[u][0];
}
int main(){
	cin >> n >> m >> s;
	for(int i = 1,u,v;i < n;i++){
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	dfs(s,0);
	init();
	while(m--){
		int u,v;
		cin >> u >> v;
		cout << lca(u,v) << "\n";
	}
	return 0;
}