前言

最近事情挤在了一堆，体测啊，申请创新奖励啊，调试环境啊...还有一系列作业和上课内容需要补
其实最近写题时间是挺少的（主要是懒 画外音:别骂了别骂了
我不是想把某杯赛的国赛和某天梯赛打完再开始补题吗 最近只想写水题

还有一个原因就是树一直就是我的弱项，主要没好好系统的学一遍 队友会写就行了（bushi
咕了好久才写了一下这题

下面是正文

思路：

  • 用邻接表连单向边后，从根节点开始dfs，每次记录以u为起点的子节点个数size[u],从根节点遍历到u结点所需要的时间dfn[u],第dfntot时刻从根节点遍历到的位置pos[dfntot]。

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=2e5+10;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,dfntot,size[N],dfn[N],pos[N];
vector<int> g[N];

void dfs(int u){
    size[u]=1;
    dfn[u]=++dfntot;
    pos[dfntot]=u;
    for(auto v:g[u]){
        dfs(v);
        size[u]+=size[v]; 
    }
}

void solve(){
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        int fa;cin>>fa;
        g[fa].pb(i);
    } 
    dfs(1);
    while(m--){
        int u,k;cin>>u>>k;
        if(size[u]<k) cout<<"-1\n";
        else cout<<pos[k+dfn[u]-1]<<"\n";
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}