← 返回题目列表

Codeforces · 685/B

B. 凯和雪花

中文机器翻译题面 查看原题

当那片魔镜击中凯的眼睛后,他对玫瑰的美丽不再感兴趣。现在他喜欢看雪花。

从前,他发现一片巨大的雪花,它的形状是由n个节点组成的树(连通无环图)。树的根索引为1。Kay 对这棵树的结构非常感兴趣。

在做了一些研究之后,他形成了 q 个他感兴趣的查询。第 i 个查询要求找到节点 vi 的子树的质心。您的目标是回答所有问题。

节点的子树是由该节点及其所有后代(直接或非)组成的树的一部分。换句话说,节点v的子树由节点u形成,使得节点v存在于从u到根的路径上。

树(或子树)的质心是一个节点,因此如果我们从树中删除它,则连接组件的最大大小将至少比初始树(或子树)的大小小两倍。

输入

输入的第一行包含两个整数 n 和 q (2 ≤ n ≤ 300 000, 1 ≤ q ≤ 300 000)——分别是初始树的大小和查询的数量。

第二行包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi ≤ n) - 从 2 到 n 的节点的父节点的索引。节点 1 是树的根。保证 pi 定义正确的树。

以下 q 行中的每一行都包含一个整数 vi (1 ≤ vi ≤ n) — 节点的索引,它定义了我们要为其找到质心的子树。

输出

对于每个查询,打印相应子树的质心索引。如果有很多合适的节点,则打印其中任何一个。保证每棵子树至少有一个质心。

示例

输入 #1

7 4
1 1 3 3 5 3
1
2
3
5

输出 #1

3
2
3
6

注意

第一个查询要求整个树的质心 - 这是节点 3。如果我们删除节点 3,树将分为四个部分,两个大小为 1,两个大小为 2。

第二个节点的子树仅由该节点组成,因此答案为 2。

节点 3 是它自己的子树的质心。

节点 5 的子树的质心是节点 5 和 6 - 两个答案都被认为是正确的。