树上旅⾏ - 编程题库

题目描述

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

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

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

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

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

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

输入格式

第⼀⾏，两个正整数n,q，分别表⽰有根树的结点数量，以及旅⾏次数。第⼆⾏，n-1个整数p₂,p₃,……,p_n,其中p_i表⽰结点i的⽗结点编号。

接下来2q行中的第2i-1行(1≤i≤q)包含两个正整数 s_i,k_i，分别表示第i次旅行的起点编号，以及移动序列的长度。第 2i 行包含k个整数a_i,1,a_i,2,·.·,a_i,k，表示移动序列。

输出格式

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

示例 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

输出:

示例 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

提示

说明/提示

子任务编号	测试点占比	$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$

题库

题库

10722.树上旅⾏