在遥远的未来,人类建立了一支星际舰队,由 N 艘战舰组成,编号从 0 到 N-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 行,每行描述一个任务:首先是一个整数 m(2 \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解释
- 第一个任务中,战舰 3 和 4 的共同上级是 2 号战舰。
- 第二个任务中,战舰 2 本身就能指挥所有参与者。
- 第三个任务中,只有旗舰 0 能指挥所有战舰。
样例2解释
- 前四个任务的最佳指挥官均为 1 号或 2 号战舰,具体取决于参与任务的战舰集合。
- 最后一个任务需要旗舰 0 作为指挥官。
时间限制 | 1 秒 |
内存限制 | 128 MB |