知道是要求 lca 到根的最大值,但是还是被卡了。
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,q;
struct edge{int v,nex;}e[2*N];
int tot,head[N];
void add(int u,int v){e[++tot].v = v,e[tot].nex = head[u],head[u] = tot;}
int lg[N],dis[N],a[N],fa[N][30];
void init(){for(int i = 1;i <= n;i++)lg[i] = lg[i-1] + (1<<lg[i-1]==i);}
void dfs(int las,int u,int maxx)
{
dis[u] = dis[las] + 1;
if(u > maxx)maxx = u;a[u] = maxx;
fa[u][0] = las;
for(int i = 1;i <= lg[u];i++)
fa[u][i] = fa[fa[u][i-1]][i-1];
for(int i = head[u];i;i = e[i].nex)
if(e[i].v != las)dfs(u,e[i].v,maxx);
}
int lca(int u,int v)
{
if(dis[u] < dis[v])swap(u,v);
while(dis[u] > dis[v])u = fa[u][lg[dis[u]-dis[v]]-1];
if(u == v)return u;
for(int i = lg[dis[u]]-1;i+1;i--)
if(fa[u][i] != fa[v][i])u = fa[u][i],v = fa[v][i];
return fa[u][0];
}
int main()
{
scanf("%d",&n);
for(int i = 1;i < n;i++)
{
int x;
scanf("%d",&x);
add(i,x),add(x,i);
}
init(),dfs(0,0,0);
scanf("%d",&q);
while(q--)
{
int m,u,v;
scanf("%d%d",&m,&u);
for(int i = 2;i <= m;i++)
scanf("%d",&v),u = lca(u,v);
printf("%d\n",a[u]);
}
return 0;
}