该题代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,Q;
vector<int> g[N];
int f[N][17],dep[N];
void dfs(int x,int from)
{
dep[x]=dep[from]+1;f[x][0]=from;
for(int i=1;i<=17;i++)
{
f[x][i]=f[f[x][i-1]][i-1];
}
for(auto v:g[x])
{
if(v==from) continue;
dfs(v,x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int k=-1;
int h=dep[x]-dep[y];
while(h)
{
int c=h&1;
k++;
h=h>>1;
if(c) x=f[x][k];
}
if(x==y) return y;
for(int i=17;~i;i--)
{
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int x;
cin>>x;
g[i].push_back({x});
g[x].push_back({i});
}
memset(f,-1,sizeof(f));
dfs(0,-1);
//cout<<lca(3,4);
cin>>Q;
for(int i=1;i<=Q;i++)
{
int m;
cin>>m;
int x,y;
cin>>x>>y;
y=lca(x,y);
for(int j=3;j<=m;j++)
{
int a;
cin>>a;
}
for(int i=y;~i;i=f[y][0])
{
y=max(y,i);
}
}
return 0;
}
如果把注释改代码,就会发现按样例1 输入,得到lca(3,4)=-1,正确应该是2。 LCA错了?然而模板能过