题目描述

给定一棵 $n$ 个结点的有根树，根为 $1$。小 A 进行 $q$ 次旅行，每次从 $s_i$ 出发，按长度为 $k_i$ 的非零整数序列移动：正数表示向父结点移动对应次数，负数表示向当前结点编号最小的子结点移动对应次数；若无法移动则停在原结点。求每次旅行的终点。

输入格式

第一行输入两个正整数 $n,q$。 第二行输入 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$。 接下来每次询问占两行：第一行输入 $s_i,k_i$，第二行输入 $k_i$ 个整数 $a_{i,1},\ldots,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 \le n\le 10^5$，$1 \le q\le 2\times 10^4$，$1 \le p_i \le n$，$1 \le s_i \le n$，$k_i \ge 1$，$\sum k_i \le 10^5$，$1 \le |a_{i,j}|\le n$。
• 子任务：$20$ 满足 $n,q \le 100,\sum k_i \le 1000$ 且 $a_{i,j}in{1,-1}$；$20$ 仅含第一种移动；$20$ 仅含第二种移动。

来源

GESP 2025 年 06 月 C++ 八级 T1