A5183. [GESP202506 八级] 树上旅行
编程题
普及+/提高
知识点
题目描述
给定一棵有 $n$ 个结点的有根树，结点依次以 $1, 2, \ldots, n$ 编号，其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中，小 A 首先会选定结点 $s_i$ 作为起点，并移动若干次。移动分为以下两种：
1. 移动至当前结点的父结点。特殊地，如果当前位置于根结点，则不进行移动。
2. 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位置于叶子结点，则不进行移动。
由于移动次数可能很大，对于第 i 次旅行，旅行中的移动将以 $k_i$ 不为零的整数构成的序列 $a_{i,1}, a_{i,2}, \ldots, a_{i,k}$ 表示。对于 $a_{i,j}$，若 $a_{i,j} > 0$ 则代表进行 $a_{i,j}$ 次第一种移动；若 $a_{i,j} < 0$ 则代表进行 $-a_{i,j}$ 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中，小 A 首先会选定结点 $s_i$ 作为起点，并移动若干次。移动分为以下两种：
1. 移动至当前结点的父结点。特殊地，如果当前位置于根结点，则不进行移动。
2. 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位置于叶子结点，则不进行移动。
由于移动次数可能很大，对于第 i 次旅行，旅行中的移动将以 $k_i$ 不为零的整数构成的序列 $a_{i,1}, a_{i,2}, \ldots, a_{i,k}$ 表示。对于 $a_{i,j}$，若 $a_{i,j} > 0$ 则代表进行 $a_{i,j}$ 次第一种移动；若 $a_{i,j} < 0$ 则代表进行 $-a_{i,j}$ 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。
输入格式
第一行，两个正整数$n, q$，分别表示有根树的结点数量，以及旅行次数。
第二行，$n-1$个整数$p_2, p_3, \ldots, p_n$，其中$p_i$表示结点 i 的父结点编号。
接下来 2q 行中的第$2i-1$行（$1 \leq i \leq q$）包含两个正整数$s_i, k_i$，分别表示第 i 次旅行的起点编号，以及移动序列的长度。第$2i$行包含$k_i$个整数$a_{i,1}, a_{i,2}, \ldots, a_{i,k}$，表示移动序列。
第二行，$n-1$个整数$p_2, p_3, \ldots, p_n$，其中$p_i$表示结点 i 的父结点编号。
接下来 2q 行中的第$2i-1$行（$1 \leq i \leq q$）包含两个正整数$s_i, k_i$，分别表示第 i 次旅行的起点编号，以及移动序列的长度。第$2i$行包含$k_i$个整数$a_{i,1}, a_{i,2}, \ldots, a_{i,k}$，表示移动序列。
输出格式
输出共 q 行，第 i 行包含一个整数，表示第 i 次旅行终点的结点编号。
输入输出样例
输入 #1
5 4 1 1 2 2 3 3 1 -1 -1 2 5 1 -1 1 -1 1 5 8 1 1 1 -1 -1 -1 -1 -1 5 3 -1 -1 1
输出 #1
4 1 4 2
输入 #2
8 3 5 4 2 1 3 6 6 8 1 8 8 2 8 -8 8 3 8 -8 8
输出 #2
1 7 1
说明/提示
#### 数据范围
| 子任务编号 | 测试点占比 |$n$|$q$|$\sum k_i$| 特殊性质 |
|---|---|---|---|---|--|
| 1 | 20% |$\leq 100$|$\leq 100$|$\leq 1000$| 保证$a_{ij}$为 1 或$-1$|
| 2 | 20% |$\leq 10^4$|$\leq 10^4$|$\leq 4 \times 10^4$| 仅包含第一种移动 |
| 3 | 20% |$\leq 10^4$|$\leq 10^4$|$\leq 4 \times 10^4$| 仅包含第二种移动 |
| 4 | 40% |$\leq 10^5$|$\leq 2 \times 10^4$|$\leq 10^5$| - |
对于所有测试点，保证$1 \leq n \leq 10^5$，$1 \leq q \leq 2 \times 10^4$，$1 \leq p_i \leq n$，$1 \leq s_i \leq n$，$k_i \geq 1$且$\sum k_i \leq 10^5$，$1 \leq |a_{ij}| \leq n$。
| 子任务编号 | 测试点占比 |$n$|$q$|$\sum k_i$| 特殊性质 |
|---|---|---|---|---|--|
| 1 | 20% |$\leq 100$|$\leq 100$|$\leq 1000$| 保证$a_{ij}$为 1 或$-1$|
| 2 | 20% |$\leq 10^4$|$\leq 10^4$|$\leq 4 \times 10^4$| 仅包含第一种移动 |
| 3 | 20% |$\leq 10^4$|$\leq 10^4$|$\leq 4 \times 10^4$| 仅包含第二种移动 |
| 4 | 40% |$\leq 10^5$|$\leq 2 \times 10^4$|$\leq 10^5$| - |
对于所有测试点，保证$1 \leq n \leq 10^5$，$1 \leq q \leq 2 \times 10^4$，$1 \leq p_i \leq n$，$1 \leq s_i \leq n$，$k_i \geq 1$且$\sum k_i \leq 10^5$，$1 \leq |a_{ij}| \leq n$。