给定一棵有 n 个结点的 **有根树**,结点依次以 1,2,\dots,n 编号,其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先选定结点 s_i 作为起点,并移动若干次。移动分为以下两种:
1. 移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。
2. 移动至当前结点的所有子结点中**编号最小**的结点。特殊地,如果当前位于叶子结点,则不进行移动。
由于移动次数可能很大,对于第 i 次旅行,旅行中的移动以 k_i 个不为零的整数构成的序列 a_{i,1}, a_{i,2}, \dots, a_{i,k_i} 表示。对 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, \dots, 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}, \dots, a_{i,k_i},表示移动序列。
输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。
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
4 1 4 2
8 3 5 4 2 1 3 6 6 8 1 8 8 2 8 -8 8 3 8 -8 8
1 7 1
对于所有测试点,保证:
- 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_{i,j}| \leq n
时间限制 | 1 秒 |
内存限制 | 128 MB |