06602. GESP-8级-2025-06-树上旅行

题目描述

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

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

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

由于移动次数可能很大，对于第 $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$ 的父结点编号。

接下来 $2 q$ 行中的第 $2 i - 1$ 行（ $1 \leq i \leq q$ ）包含两个正整数 $s_{i}, k_{i}$ ，分别表示第 $i$ 次旅行的起点编号，以及移动序列的长度。第 $2 i$ 行包含 $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

输出

数据范围

子任务编号	测试点占比	$n$	$q$	$\sum k_{i}$	特殊性质
$1$	$20%$	$\leq 100$	$\leq 100$	$\leq 1000$	保证 $a_{i, j}$ 为 $1$ 或 $- 1$
$2$	$20%$	$\leq 1 0^{4}$	$\leq 1 0^{4}$	$\leq 4 \times 1 0^{4}$	仅包含第一种移动
$3$	$20%$	$\leq 1 0^{4}$	$\leq 1 0^{4}$	$\leq 4 \times 1 0^{4}$	仅包含第二种移动
$4$	$40%$	$\leq 1 0^{5}$	$\leq 2 \times 1 0^{4}$	$\leq 1 0^{5}$	-

对于所有测试点，保证：

$1 \leq n \leq 1 0^{5}$
$1 \leq q \leq 2 \times 1 0^{4}$
$1 \leq p_{i} \leq n$
$1 \leq s_{i} \leq n$
$k_{i} \geq 1$ 且 $\sum k_{i} \leq 1 0^{5}$
$1 \leq ∣ a_{i, j} ∣ \leq n$

来源：洛谷 P13019（CCF GESP 8 级上机题）

06602. GESP-8级-2025-06-树上旅行 未做

题目描述

输入格式

输出格式

样例

数据范围

06602. GESP-8级-2025-06-树上旅行未做