Military Problem

DFS序模板题了，l[rt]标记rt节点第一次进入，r[rt]表示rt节点退出，
然后只要判断l[rt] + k - 1 是否小于等于r[rt]即可。

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

vector<int> G[N];

int id[N], l[N], r[N], rk[N], tot, n, m;

void dfs(int rt, int fa) {
    id[rt] = ++tot;
    rk[tot] = rt;
    l[rt] = tot;
    for(auto i : G[rt]) {
        if(i == fa) continue;
        dfs(i, rt);
    }
    r[rt] = tot;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d", &n, &m);
    for(int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        G[x].push_back(i);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i++) {
        int rt, k;
        scanf("%d %d", &rt, &k);
        printf("%d\n", l[rt] + k - 1 <= r[rt] ?  rk[l[rt] + k - 1] : -1);
    }
    return 0;
}