A67405. 树上旅行

试题名称：树上旅行

时间限制：1.0 s

内存限制：512.0 MB

题目描述

给定一棵有 n 个结点的有根树，结点依次以1,2,....n 编号，其中根结点的编号为 1 。

小 A 计划在这棵有根树上进行 q次旅行。在第 i 次旅行中，小 A 首先会选定结点 s_i作为起点，并移动若干次。移动分为以下两种：

1. 移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。

2. 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。

由于移动次数可能很大，对于第 i 次旅行，旅行中的移动将以 k_i 个不为零的整数构成的序列 表示。对于 a_ij ，若 a_ij>0则代表进行 a_ij次第一种移动；若a_ij <0 则代表进行-a_ij 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

3.1.2 输入格式

第一行，两个正整数 n,q，分别表示有根树的结点数量，以及旅行次数。

第二行，n-1 个整数p₂,p₃....p_n，其中p_i 表示结点 i 的父结点编号。

接下来 2q行中的第 2i-1 行（1<=i<=q ）包含两个正整数 s_i,k_i，分别表示第 i 次旅行的起点编号，以及移动序列的长度。第 2i 行包含 k_i个整数 ，表示移动序列。

3.1.3 输出格式

输出共 q 行，第 i 行包含一个整数，表示第  i 次旅行终点的结点编号。

3.1.4 样例

3.1.4.1 输入样例 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

3.1.4.2 输出样例 1

4

1

4

2

3.1.4.3 输入样例 2

8 3

5 4 2 1 3 6 6

8 1

8

8 2

8 -8

8 3

8 -8 8

3.1.4.4 输出样例 2

1

7

1

3.1.5 数据范围