```
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int n, m, s;
int depth[500005], fa[500005][25];
int lg[500005];
vector<int> g[500005];
void init_lg()
{
lg[1] = 0;
for (int i = 2; i <= n; i++)
{
lg[i] = lg[i / 2] + 1;
}
}
void dfs(int now, int fath)
{
depth[now] = depth[fath] + 1;
fa[now][0] = fath;
for (int i = 1; i <= lg[depth[now]]; i++)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (int i = 0; i < g[now].size(); i++)
{
if(g[now][i] != fath)
dfs(g[now][i], now);
}
}
int lca(int x, int y)
{
if (depth[x] < depth[y]) swap(x, y);
while (depth[x] > depth[y])
x = fa[x][lg[depth[x] - depth[y]]];
if (x == y) return x;
for (int i = lg[depth[x]]; i >= 0; i--)
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int main()
{
scanf("%d %d %d", &n, &m, &s);
int from, to;
for (int i = 0; i < n - 1; i++)
{
scanf("%d %d", &from, &to);
g[from].push_back(to);
g[to].push_back(from);
}
init_lg();
dfs(s, 0);
for (int i = 0; i < m; i++)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}
```
by dctc1494 @ 2024-03-02 08:29:18
@[dctc1494](/user/773235) 十分感谢！原来是我建图的时候搞错了，题目里没有说输入的边一定是子节点和父节点的关系。
by JOEYyyyyfuck @ 2024-03-03 00:08:29
另本贴终结！审题杀我！orz
by JOEYyyyyfuck @ 2024-03-03 00:08:59