附议 $RE$ 加 $MLE$ :
```cpp
#include <stdio.h>
#include <vector>
using namespace std;
int n, q, dep[200007];
vector<int> ance[200007];
int main(){
dep[1] = n;
scanf("%d%d", &n, &q);
for(int i = 2; i <= n; i ++){
int e;
scanf("%d", &e);
ance[i].push_back(e);
for(int j = 0; true; j ++){
if((int) ance[ ance[i][j] ].size() - 1 < j) break;
else ance[i].push_back( ance[ ance[i][j] ][j] );
}
} for(int i = 2; i <= n; i ++) dep[i] = dep[ ance[i][0] ] + 1;
for(int i = 0; i < q; i ++){
int x, y, power;
scanf("%d%d", &x, &y);
if(dep[x] > dep[y]){
power = 0;
int up = (int) (dep[x] - dep[y]);
while(up){
if(up % 2) x = ance[x][power];
power ++;
up /= 2;
}
} else if(dep[x] < dep[y]){
power = 0;
int up = (int) (dep[y] - dep[x]);
while(up){
if(up % 2) y = ance[y][power];
power ++;
up /= 2;
}
} if(x == y) printf("%d\n", x);
else{
for(int j = ance[x].size() - 1; j >= 0; j --){
if(ance[x][j] != ance[y][j]){
x = ance[x][j];
y = ance[y][j];
}
} printf("%d\n", ance[x][0]);
}
} return 0;
}
```
by wyf_550283 @ 2024-01-23 14:06:24
-对于threesendark的程序:dfs部分有误.
问题在于如果一个点没在搜过了,就不能重新搜了,但你的程序没考虑这一问题.改正建议:
```cpp
#include<bits/stdc++.h>
#define int long long//为啥没写呀?
......
bool vis[1000010];
void dfs(int u,int fa)
{
if(vis[u])return;vis[u]=true;
......
}
```
这就对了.
提示:下次把代码发到网上时记得给点注释.
-对于 wyf_550283 的,实在抱歉,没时间看了.
by Whycmd @ 2024-01-23 17:09:08
@[threesendark](/user/291509)
by Whycmd @ 2024-01-23 21:42:30