[AdditionalFile5355.zip](file://AdditionalFile5355.zip?type=additional_file)

#5355. 「OOI 2025 Day 1」梦想无害

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2025 Day1 T3 「Мечтать не вредно / Dreaming is not harmful」。

在一家婚礼机构 M，员工们面临大规模裁员的风险。然而，员工们却无心工作，而是忙于计算在理想情况下自己需要多少天才能成为公司负责人。

公司的组织结构是一棵悬挂的树，根节点为编号为 $1$ 的顶点。员工编号为 $v$ 的直接上级是编号为 $p_v$ 的员工。员工 $v$ 的能力水平由参数 $s_v$ 表示，每个员工的能力水平各不相同。能力水平越高，员工对公司的价值越大。需要注意的是，由于招聘过程的不透明，可能存在能力较低的员工担任能力较高员工的上级的情况。

由于大规模的人事调整，每天都会有一位总经理（位于工作层级的根节点）被解雇。如果公司还有员工，职位将由能力水平最高的直接下属接任。原总经理的其他下属将成为新总经理的下属。有关更多细节，请参考样例解释。

每位员工都轻易计算出了自己需要多少天才能成为总经理。然而，许多人不愿意等待那么久，因为担任总经理只有一天的机会！为了加速这一过程，他们愿意「取消」一位同事。被「取消」的员工能力水平会降至 $0$，因为没有人再愿意与其合作。

你需要回答 $q$ 个查询。在第 $k$ 个查询中，编号为 $v_k$ 的员工想知道，如果他“取消”恰好一位同事，自己最少需要多少天才能成为公司负责人。所有查询都是独立的假设场景，员工的实际能力水平在所有查询中保持不变。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 300000, 1 \leq q \leq n)$，分别表示员工数量和查询数量。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$ $(1 \leq p_i < i)$，表示编号为 $2$ 到 $n$ 的员工的直接上级。

第三行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$ $(1 \leq s_i \leq n)$，表示员工的能力水平。保证所有能力水平各不相同。

第四行包含 $q$ 个整数 $v_1, v_2, \ldots, v_q$ $(1 \leq v_i \leq n)$，表示查询中涉及的员工编号。保证所有 $v_i$ 各不相同。

输出格式

输出 $q$ 个整数，用空格分隔，分别表示员工 $v_1, v_2, \ldots, v_q$ 最少需要多少天才能成为总经理。

样例

输入

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

输出

1 3 0 2

在样例中，编号为 $5$ 的员工可以在 $1$ 天内成为总经理。为此，只需「取消」编号为 $2$ 的员工。公司结构的变化如下：

编号为 $3$ 的员工可以在 $3$ 天内成为总经理。为此，只需「取消」编号为 $5$ 或 $4$ 的员工。如果“取消”编号为 $5$ 的员工，公司结构的变化如下：

编号为 $1$ 的员工已经是公司负责人，因此对于相应的查询，答案为 $0$。

编号为 $4$ 的员工可以在 $2$ 天内成为总经理。类似上述示例，只需「取消」编号为 $5$ 的员工即可。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。