解题思路

我们首先运行一次 DFS（从顶点 $1$ 开始），并在进入每个顶点 $v$ 时将其推入向量 $p$ 中。设：

• $tin_v$ 表示顶点 $v$ 在向量 $p$ 中的位置（即进入 $v$ 时 $p$ 的大小）；
• $tout_v$ 表示离开顶点 $v$ 后第一个被推入向量 $p$ 的位置（即从 $v$ 的 DFS 返回时 $p$ 的大小）。

显然，顶点 $v$ 的子树中的所有顶点恰好位于区间 $[tin_v, tout_v)$ 内。

完成 DFS 后，我们可以回答查询。对于第 $i$ 个查询 $(v_i, k_i)$，计算：

$$pos_i = v_i + k_i - 1$$

如果 $pos_i \ge n$，则第 $i$ 个查询的答案为 $-1$。

否则，我们需要检查顶点 $p_{pos_i}$ 是否在顶点 $v_i$ 的子树中。顶点 $a$ 在顶点 $b$ 的子树中当且仅当：

$$tin_a \ge tin_b \quad \text{且} \quad tout_a \le tout_b $$

如果 $p_{pos_i}$ 不在 $v_i$ 的子树中，则答案为 $-1$；否则答案为 $p_{pos_i}$。

总时间复杂度为 $O(n + q)$。

#include <bits/stdc++.h>

using namespace std;

int n, q;
vector<vector<int>> tree;

int current_preorder;
vector<int> preorder, max_preorder;
vector<int> sorted_by_preorder;

void Dfs(int w) {
  sorted_by_preorder[current_preorder] = w;
  preorder[w] = current_preorder++;
  for (int c : tree[w]) {
    Dfs(c);
  }
  max_preorder[w] = current_preorder - 1;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  assert(2 <= n);
  assert(1 <= q);
  tree.resize(n);
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    p--;
    assert(0 <= p and p < n);
    tree[p].push_back(i);
  }

  preorder.resize(n);
  max_preorder.resize(n);
  sorted_by_preorder.resize(n);
  current_preorder = 0;
  Dfs(0);

  for (int i = 0; i < q; i++) {
    int u, k;
    cin >> u >> k;
    u--; k--;
    assert(0 <= u and u < n);
    assert(0 <= k and k < n);
    k += preorder[u];
    int answer = -1;
    if (k <= max_preorder[u]) {
      answer = sorted_by_preorder[k] + 1;
      assert(1 <= answer and answer <= n);
    }
    cout << answer << '\n';
  }
  return 0;
}