题目：
```
【问题描述】
给你一棵有根树，要求你计算出
�
对结点的最近公共祖先。
【输入格式】
输入文件的第一行包含两个整数
�
和
�
（
2
≤
�
,
�
≤
2
×
10
5
），其中
�
为结点个数，结点编号为
1
到
�
；
�
表示询问次数。
接下来
�
−
1
行，每行两个整数
�
和
�
，表示结点
�
是结点
�
的父亲结点；
接下来的
�
行，每行两个整数
�
和
�
，要求计算出结点
�
和
�
的最近公共祖先。
【输出格式】
输出文件共
�
行，分别为每对结点的最近公共祖先编号。
【样例输入1】
5 3
2 3
3 4
3 1
1 5
3 5
4 5
1 2
【样例输出1】
3
3
2
【样例1解释】
无。
【数据范围及约定】
对于所有数据，
2
≤
�
,
�
≤
2
×
10
5
。
```
by zyc_bot @ 2024-03-24 16:39:38
@[zyc_bot](/user/1076445) @[vflower](/user/1000066)
by zyc_bot @ 2024-03-24 16:44:53
`if (p[a][i - 1] != -1 ` 应该是 p[a][i] 吧，或者直接去掉呢
by vflower @ 2024-03-24 16:55:51
........
by lyf15320155500 @ 2024-03-24 16:58:49
@[zyc_bot](/user/1076445)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 2e5 + 10, M = 2 * N;
int n, m;
int rt;
int p[N][35];
int h[N], e[M], ne[M], idx, d[N], fa[N];
inline void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
inline void dfs(int x, int de)
{
d[x] = de;
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
// if (e[i] == fa[x]) continue;
dfs(j, de + 1);
}
}
inline void init()
{
for (int i = 1; i <= n; i ++ ) p[i][0] = fa[i];
for (int j = 1; (1 << j) <= n; j ++ )
for (int i = 1; i <= n; i ++ )
p[i][j] = p[p[i][j - 1]][j - 1];
}
inline int lca(int a, int b)
{
int k = 20;
for (int i = k; i >= 0; i -- )
if (d[a] - (1 << i) >= d[b])
a = p[a][i];
if (a == b) return a;
for (int i = k; i >= 0; i -- )
if (p[a][i] != p[b][i]) a = p[a][i], b = p[b][i];
return p[a][0];
}
int main()
{
// memset(fa, -1, sizeof fa);
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
int nc = n - 1, x, y;
while (nc -- )
{
scanf("%d%d", &x, &y);
add(x, y);
// add(y, x);
fa[y] = x;
}
rt = 1;
while (fa[rt] != 0) rt = fa[rt];
/* for (int i = 1; i <= n; i ++ )
if (fa[i] == 0)
{
rt = i;
break;
}*/
dfs(rt, 1);
// for (int i = 1 ; i <= n; i ++ ) cout << d[i] << '\n';
init();
while (m -- )
{
scanf("%d%d", &x, &y);
if (d[x] < d[y]) swap(x, y);
printf("%d\n", lca(x, y));
}
return 0;
}
```
by wxb_sql @ 2024-03-24 17:30:47
@[zyc_bot](/user/1076445) hello
by sunhaoyun @ 2024-03-24 18:37:23