5217. 公司查询（Company Queries I）
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 给定一个包含 $n$ 个员工的公司组织结构，该结构可以看作一棵以 $1$ 号节点为根的有根树： - 员工编号依次为 $1, 2, \dots, n$。 - 员工 $1$ 是总负责人，也就是这棵树的根节点。 - 除了总负责人外，每个员工都有且仅有一个直接上级。 你需要处理 $q$ 个查询，每个查询给出两个整数 $x$ 和 $k$，要求找出：**员工 $x$ 的第 $k$ 级上级是谁？** （注：直接上级为第 $1$ 级上级，直接上级的直接上级为第 $2$ 级上级，以此类推。如果不存在这样的上级，输出 `-1`。） ## 输入格式 第一行包含两个整数 $n, q$，分别表示员工数量和查询数量。 第二行包含 $n-1$ 个整数 $e\_2, e\_3, \dots, e\_n$，其中 $e\_i$ 表示员工 $i$ 的直接上级（$2 \le i \le n$）。 接下来 $q$ 行，每行包含两个整数 $x, k$，表示一个查询。 ## 输出格式 对于每个查询，输出一行一个整数，表示查询的答案。若不存在，则输出 `-1`。 ## 输入输出样例 ### 输入样例 1 ``` 5 3 1 1 3 3 4 1 4 2 4 3 ``` ### 输出样例 1 ``` 3 1 -1 ``` ## 提示/说明 ### 样例 1 解释 公司组织结构树形图如下： - $1$ 号员工为总负责人； - $2, 3$ 号员工的直接上级是 $1$； - $4, 5$ 号员工的直接上级是 $3$。 对于查询： - **`4 1`**：询问 $4$ 号员工的第 $1$ 级上级，即直接上级，为 $3$； - **`4 2`**：询问 $4$ 号员工的第 $2$ 级上级，即 $3$ 的直接上级，为 $1$； - **`4 3`**：询问 $4$ 号员工的第 $3$ 级上级，由于总负责人 $1$ 没有更上级的负责人，因此不存在，输出 `-1`。 ### 数据规模与约定 对于所有数据，保证： - $1 \le n, q \le 2 \times 10^5$； - $1 \le e\_i \le i - 1$； - $1 \le x, k \le n$。