#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 500005
int n,m,q,dep[MAXN],p[MAXN][22],hum[MAXN],mx[MAXN];
vector<int> g[MAXN];
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    p[u][0]=fa;
    for (int i=1;i<=20;i++) 
        p[u][i]=p[p[u][i-1]][i-1];
    for (int i=0;i<g[u].size();i++)
        if (g[u][i]!=fa) 
            mx[g[u][i]]=max(mx[u],g[u][i]),dfs(g[u][i],u);
}
bool cmp (int a,int b)
{
    return dep[a]<dep[b];
}
int lca()
{
    sort(hum+1,hum+m+1,cmp);
    for (int i=20;i>=0;i--)
        for (int j=2;j<=m;j++)
            if (dep[p[hum[j]][i]]>=dep[hum[1]])
                hum[j]=p[hum[j]][i];
    int ok=1;
    for (int j=2;j<=m;j++)
        if (hum[j-1]!=hum[j])
        {
            ok=0;break;
        }
    if (ok) return mx[hum[1]];
    for (int i=20;i>=0;i--)
    {
        ok=0;
        for (int j=2;j<=m;j++)
            if (p[hum[j]][i]!=p[hum[1]][i])
            {
                ok=1;break;
            } 
        if (ok)
            for (int j=1;j<=m;j++) hum[j]=p[hum[j]][i];
    }
    return mx[p[hum[1]][0]];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for (int i=1;i<=n-1;i++)
    {
        int v;
        cin>>v;
        g[i].push_back(v); 
        g[v].push_back(i); 
    }
    dfs(0,0);
    cin>>q;
    while(q--)
    {
        cin>>m;
        for (int i=1;i<=m;i++) cin>>hum[i];
        cout<<lca()<<endl;
    }
    return 0;
}

洛谷ac,但是vijos拿不满

0 条评论

目前还没有评论...

信息

ID
2564
难度
9
分类
(无)
标签
递交数
89
已通过
3
通过率
3%
上传者