题目描述

给定一棵 $n$ 个节点的树。

节点的编号为 $1 \sim n$，其中 $1$ 号节点为根节点，每个节点的编号都大于其父节点的编号。

现在，你需要回答 $q$ 个询问。

每个询问给定两个整数 $u_i,k_i$。

我们希望你用 DFS（深度优先搜索）算法来遍历根节点为 $u_i$ 的子树。

我们规定，当遍历（或回溯）到某一节点时，下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。

例如，上图实例中：

• 如果遍历根节点为 $1$ 号节点的子树，则子树内各节点的遍历顺序为 $[1,2,3,5,6,8,7,9,4]$。
• 如果遍历根节点为 $3$ 号节点的子树，则子树内各节点的遍历顺序为 $[3,5,6,8,7,9]$。
• 如果遍历根节点为 $7$ 号节点的子树，则子树内各节点的遍历顺序为 $[7,9]$。
• 如果遍历根节点为 $9$ 号节点的子树，则子树内各节点的遍历顺序为 $[9]$。

每个询问就是让你计算采用规定的 DFS 算法来遍历根节点为 $u_i$ 的子树时，第 $k_i$ 个被遍历到的节点的编号。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n-1$ 个整数 $p_2,p_3,…,p_n$，其中 $p_i$ 表示第 $i$ 号节点的父节点的编号。

接下来 $q$ 行，每行包含两个整数 $u_i,k_i$，表示一组询问。

输出格式

共 $q$ 行，每组询问输出一行一个整数表示第 $k_i$ 个被遍历到的节点的编号。

如果第 $k_i$ 个被遍历到的节点不存在，则输出 $-1$。

数据范围

前三个测试点满足 $2 \le n \le 20$，$1 \le q \le 20$。
所有测试点满足 $2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le p_i < i$，$1 \le u_i,k_i \le n$。

输入样例：

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

输出样例：

3
6
8
-1
9
4

算法

DFS $O(nlog(n))$

本题是一个经典的DFS序列问题(DFS前序遍历)

难点：

• 观察并发现子树上的所有点在答案序列中都是连续的。
• 预处理出答案序列（树的前序遍历序列）。
• 子树中第 $i$ 个节点就是前序遍历中树根后第 $i - 1$ 个节点。
• 预处理出各个点在前序遍历中的位置即可在 $O(1)$ 的时间内实现查询。

时间复杂度

• 前期预处理时间复杂度为 $O(nlog(n))$.
• 查询时间复杂度为 $O(q)$，单次查询时间为 $O(1)$。

空间复杂度

• 空间复杂度为$O(n)$

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5 + 5;
int st[N], num[N];
vector<int> h[N], ans;
int dfs(int u) {
    int sum = 1;
    ans.push_back(u);
    for (auto x : h[u]) sum += dfs(x);
    return num[u] = sum;
}
int main() {
    int n, q; cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        h[p].push_back(i);
    }
    for (int i = 1; i <= n; i++) sort(h[i].begin(), h[i].end());
    dfs(1);
    int t = 0;
    for (auto x : ans) st[x] = t++;
    while (q--) {
        int u, k; cin >> u >> k;
        if (k > num[u]) puts("-1");
        else cout << ans[st[u] + k - 1] << endl;
    }
    return 0;
}