题目：$\textsf{\textcolor{#FFC116}{P3379 【模板】最近公共祖先（LCA）}}$。
提交记录：
- 正确记录：R237935271。
错误原因：
-
21 行，在 x 的祖先节点的深度等于 y 时也要跳，否则跳不到 y。
错误示范：
for (int i = 19; i >= 0; i--) if (deep[fa[x][i]] > deep[y]) x = fa[x][i];正解：
for (int i = 19; i >= 0; i--) if (deep[fa[x][i]] >= deep[y]) x = fa[x][i]; -
$\log 5 \times 10^5 \approx 19$，数组要开下标 $0 \sim 19$ 即 $20$。
错误示范：
int n, m, s, deep[LEN], fa[LEN][19];正解：
int n, m, s, deep[LEN], fa[LEN][20];
#include <bits/stdc++.h>
using namespace std;
const int LEN = 5e5 + 5;
vector<int> G[LEN];
int n, m, s, deep[LEN], fa[LEN][20];
void dfs(int x, int father)
{
deep[x] = deep[father] + 1;
fa[x][0] = father;
for (int i = 1; (1 << i) <= deep[x]; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = 0; i < G[x].size(); i++)
if (G[x][i] != father)
dfs(G[x][i], x);
}
int lca(int x, int y)
{
if (deep[x] < deep[y])
swap(x, y);
for (int i = 19; i >= 0; i--)
if (deep[fa[x][i]] >= deep[y])
x = fa[x][i];
if (x == y)
return x;
for (int i = 19; i >= 0; i--)
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n - 1; i++)
{
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(s, 0);
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
cout << lca(a, b) << "\n";
}
return 0;
}