P13019 [GESP202506 八级] 树上旅行

给定一棵有 $ 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$ 次旅行终点的结点编号。

| 子任务编号 | 测试点占比 | $n$ | $q$ | $\sum k_i$ | 特殊性质 | |:-:|:-:|:-:|:-:|:-:|:-:| | $1$ | $20\%$ | $\leq 100$ | $\leq 100$ | $\leq 1000$ | 保证 $a_{i,j}$ 为 $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_{i,j}| \leq n$