开始: 2025-07-04 17:00:00

暑假训练赛03专题:逆元,组合数,倍增算法

结束: 2025-07-04 21:00:00
当前  2025-07-17 20:00:30  类型: IOI  状态: 已经结束 

P5. 星际舰队
描述

在遥远的未来,人类建立了一支星际舰队,由 N 艘战舰组成,编号从 0N-1。其中,0 号战舰是旗舰,其余每艘战舰都有且仅有一位直接指挥官。具体来说,编号为 i 的战舰的直接指挥官是 f_i 号战舰。

星际舰队遵循严格的指挥系统:每艘战舰只能接受来自自身、直接上级或间接上级的命令。

换句话说,战舰 x 可以指挥战舰 y,当且仅当 x=y,或 x=f_y,或 x 可以指挥 f_y。特别地,旗舰 0 号战舰只能由自身指挥,不接受任何其他战舰的命令。

现在,舰队需要执行一系列联合任务,每次任务需要选出一艘战舰作为指挥官。这位指挥官必须能够指挥参与任务的所有战舰。如果有多个符合条件的战舰,选择编号最大的那艘。请你编写程序,帮助舰队完成指挥官的选择。

N\leq 10^6

输入

- 第一行包含一个整数 N,表示战舰的数量。

- 第二行包含 N-1 个整数,依次为 f_1, f_2, \dots, f_{N-1},表示每艘战舰的直接指挥官。

- 第三行包含一个整数 Q,表示任务的数量。

- 接下来 Q 行,每行描述一个任务:首先是一个整数 m2 \leq m \leq N),表示参与本次任务的战舰数量;随后是 m 个不同的整数,表示参与任务的战舰编号。


输出

输出 Q 行,每行一个整数,表示每个任务的最佳指挥官编号。

样例

输入

5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4

输出

2
2
0

输入

7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4

输出

2
1
1
1
0
提示

样例1解释

  - 第一个任务中,战舰 34 的共同上级是 2 号战舰。

  - 第二个任务中,战舰 2 本身就能指挥所有参与者。

  - 第三个任务中,只有旗舰 0 能指挥所有战舰。

样例2解释

  - 前四个任务的最佳指挥官均为 1 号或 2 号战舰,具体取决于参与任务的战舰集合。

  - 最后一个任务需要旗舰 0 作为指挥官。


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交