1. 问题描述：
给定一棵 n 个节点的树。节点的编号为 1∼n，其中 1 号节点为根节点，每个节点的编号都大于其父节点的编号。现在，你需要回答 q 个询问。每个询问给定两个整数 ui，ki。我们希望你用 DFS（深度优先搜索）算法来遍历根节点为 ui 的子树。我们规定，当遍历（或回溯）到某一节点时，下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。
例如，上图实例中：
如果遍历根节点为 1 号节点的子树，则子树内各节点的遍历顺序为 [1,2,3,5,6,8,7,9,4]。
如果遍历根节点为 3 号节点的子树，则子树内各节点的遍历顺序为 [3,5,6,8,7,9]。
如果遍历根节点为 7 号节点的子树，则子树内各节点的遍历顺序为 [7,9]。
如果遍历根节点为 9 号节点的子树，则子树内各节点的遍历顺序为 [9]。
每个询问就是让你计算采用规定的 DFS 算法来遍历根节点为 ui 的子树时，第 ki 个被遍历到的节点的编号。
输入格式
第一行包含两个整数 n，q。第二行包含 n − 1 个整数 p2，p3，…，pn，其中 pi 表示第 i 号节点的父节点的编号。接下来 q 行，每行包含两个整数 ui，ki，表示一组询问。
输出格式
共 q 行，每组询问输出一行一个整数表示第 ki 个被遍历到的节点的编号。如果第 ki 个被遍历到的节点不存在，则输出 −1。
数据范围
前三个测试点满足 2 ≤ n ≤ 20，1 ≤ q ≤ 20。
所有测试点满足 2 ≤ n ≤ 2 × 10 ^ 5，1 ≤ q ≤ 2 × 10 ^ 5，1 ≤ pi < i，1 ≤ ui，ki ≤ 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
来源：https://www.acwing.com/problem/content/description/4313/
2. 思路分析：
分析题目可以知道其实考察的是树的前序遍历，其中需要使用到的一个性质：每一棵子树在dfs的前序遍历中一定是连续的一段，根据这个性质我们就比较好处理了，我们可以在前序遍历的序列中找到节点u对应的位置，往后移动k - 1个位置就是我们要求解的答案的位置，找到这个位置对应的编号即可。所以我们可以使用数组p来存储数字的编号，q存储编号对应的位置，在dfs遍历节点的过程中更新p和q，最终根据p，q的值输出对应的答案即可。
3. 代码如下：
由于数据规模比较大所以提交上去爆栈了：
import collections
from typing import List
import sysclass Solution:count, mp = None, Nonedef dfs(self, u: int, p: List[int], q: List[int], g: List[List[int]]):# count可以理解为下标p[self.count] = uself.mp[u] = 1q[u] = self.countself.count += 1for next in g[u]:self.dfs(next, p, q, g)self.mp[u] += self.mp[next]def process(self):n, m = map(int, input().split())g = [list() for i in range(n + 10)]a = list(map(int, input().split()))# 创建有向图for i in range(n - 1):g[a[i]].append(i + 2)for i in range(1, n + 1):if g[i]:# 当前节点的子树按照节点编号从小到大排序g[i].sort()# p存储第i个点对应的编号, q存储编号为i对应的下标p, q = [0] * (n + 10), [0] * (n + 10)self.count = 0# mp用来计算节点的子树对应的节点数目, 用来判断是否有解self.mp = collections.defaultdict(int)self.dfs(1, p, q, g)for i in range(m):u, k = map(int, input().split())if self.mp[u] < k: print(-1)else:# 找到对应的位置之后对应位置的编号就是答案print(p[q[u] + k - 1])if __name__ == '__main__':# 设置最大递归调用次数sys.setrecursionlimit(1000000)Solution().process()
