Military Problem

不知道为什么这么裸...

vec存图排个序

然后按照dfs的顺序给节点小到大编号

顺被维护一个表示节点编号是的是哪个节点...

#include <bits/stdc++.h>
using namespace std;
const int maxn = 8e5+10;
struct edge{
    int to,nxt;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v){
    d[++cnt] = (edge){v,head[u]},head[u]=cnt;
}
int id[maxn],num,n,q,siz[maxn],idf[maxn];
vector<int>vec[maxn];
void dfs(int u,int fa)
{
    id[u] = ++num; siz[u] = 1, idf[num] = u;
    for(int i=0;i<vec[u].size();i++ )
    {
        int v=vec[u][i];
        if( v==fa )    continue;
        dfs(v,u);
        siz[u] += siz[v];
    }
}
int main()
{
    cin >> n >> q;
    for(int i=2;i<=n;i++)
    {
        int x; cin >> x;
        vec[x].push_back(i);
    }
    for(int i=1;i<=n;i++)    
        sort( vec[i].begin(),vec[i].end() );
    dfs(1,0);
    while( q-- )
    {
        int u,k;
        scanf("%d%d",&u,&k);
        if( siz[u]<k  )    cout << -1 << "\n";
        else     cout << idf[ id[u]+k-1 ] << "\n";
    }
}