近似二分思想
询问 x，y的 lca
设y更深
"假设有一个 dad[][] 数组
dad[x][j] 表示 x 的 2^j 级 祖先
例如 dad[x][0] 是 x 的 baba
dad[x][1] 是 x 的 yeye （baba 的 baba）
dad[x][2] 是 x 的 yeye 的 yeye
所以递推式 dad[x][j+1] = dad[ dad[x][j] ][ j ](套上 上两行就理解了)"
其实 有了递推式 dad[][]数组 就可求了
1 将 y 跳到与 x 深度一样的 那一层
如果 x == y 则返回 x 或 y
（这是 x 与 y 在一条链上的情况
如 LCA（4,2）=2
4 上升到 与 2 同层
发现 与 2 重合
则 返回 2）
2 两点 同时 倍增
若 满足 x ，y 的 2^j 级祖先不同（此祖先 在 lca祖先 下方）
则 同时 上跳 2^j 级
最后 返回 x （或 y）的 父亲
（这是 x 与 y 不在一条链上的情况
如 LCA（8 ,6）=1
8 上升到 与 6 同层
` 8-->7
发现 不与 6 重合
则
若上升 2 层（2^1）
由于 7 与 6 的 2 级 祖先 均为 1
于是 尝试 上升 1 层（2^0）
由于 7 与 6 的 1 级 祖先 不同
所以 7-->2 , 6-->5
倍增结束
因为 最后一个是 2^0 级祖先 ， (-1）就不合法了
返回 2（或5）的 父亲 1
即 lca（8,6））
# include <iostream>
# include <cstdio>
# include <cstring>
# include <string>
# include <cmath>
# include <vector>
# include <map>
# include <queue>
# include <cstdlib>
# define MAXN 500001
using namespace std;
int n, m, s;
int f[MAXN][25], deep[MAXN];//f[i][j] 为 i 的 2^j 级祖先
vector <int> vec[MAXN];
int get_num() {
int k = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
return k * f;
}
void dfs(int u)//预处理 深度， f数组
{
int i, v;
deep[u] = deep[f[u][0]] + 1;
for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i];
for(i = 0; i < vec[u].size(); i++)
{
v = vec[u][i];
if(!deep[v]) f[v][0] = u, dfs(v);
}
}
int lca(int x, int y)//倍增 求 lca
{
int i;
if(deep[x] < deep[y]) swap(x, y);
for(i = 20; i >= 0; i--)
if(deep[f[x][i]] >= deep[y])
x = f[x][i];
if(x == y) return x;
for(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()
{
int i, x, y;
n = get_num();
m = get_num();
s = get_num();
for(i = 1; i < n; i++)
{
x = get_num();
y = get_num();
vec[x].push_back(y);
vec[y].push_back(x);
}
dfs(s);
for(i = 1; i <= m; i++)
{
scanf("%d %d", &x, &y);
printf("%d
", lca(x, y));
}
return 0;
}