第 3 题 做梦无害 (dreamingisnotharmful)

时间限制 2 秒 · 空间限制 256 MB

本题使用文件输入输出：输入文件 dreamingisnotharmful.in，输出文件 dreamingisnotharmful.out。

题目描述

婚庆公司 M 计划大规模裁员。所有员工都在忙着数日子，盼着形势好转时能取代老板的位置，而不是干活。

公司的结构是一棵以 1 号顶点为根的树。编号为 $v$ 的员工的直接上司是编号为 $p_v$ 的员工。编号为 $v$ 的员工的能力水平由参数 $s_v$ 给出。所有员工的这个参数互不相同。能力水平越高，员工对公司就越有用。注意由于招聘流程不透明，可能会出现能力较弱的员工是一个能力较强员工的上司的情况。

由于重大的人事重组，每天这位位于工作层级根部的 CEO 都会被解雇。如果公司中还有员工，那么能力最强的直接下属将接替他的位置。此后，前任主管的其他下属将成为新主管的下属。更清楚地理解题意请参见样例解释。

每位员工都轻松地算出了自己成为 CEO 需要多少天。许多人没准备好等那么久，因为他们只能当一天的主管！为了加速这一过程，他们准备「注销」自己的一位同事。被「注销」的员工能力水平降为 0，因为再也没人愿意和他打交道了。

你需要回答 $q$ 个询问。在第 $k$ 个询问中，编号为 $v_k$ 的员工感兴趣的是：如果他愿意「注销」恰好一名员工，那么最少需要多少天他才能领导公司。所有询问都是假想的且相互独立，员工的真实能力水平在所有询问中都保持不变。

输入格式

第一行包含两个整数 $n$，$q$（$2 \le n \le 300\,000$，$1 \le q \le n$）——员工数量和询问数量。

第二行包含 $n - 1$ 个整数 $p_2$，$p_3$，…，$p_n$（$1 \le p_i < i$）——编号从 2 到 $n$ 的员工的直接上司。

第三行包含 $n$ 个整数 $s_1$，$s_2$，…，$s_n$（$1 \le s_i \le n$）——员工的能力水平。保证它们互不相同。

第四行包含 $q$ 个整数 $v_1$，$v_2$，…，$v_q$（$1 \le v_i \le n$）——晋升询问。保证所有数 $v_i$ 互不相同。

输出格式

输出 $q$ 个用空格分隔的整数——员工 $v_1, v_2, \ldots, v_q$ 分别成为主管所需的最少天数。

样例

样例 1

输入：

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

输出：

1 3 0 2

提示

样例解释

在样例中，第五位员工可以在 1 天后领导公司。为此，只需「注销」第二位员工。公司的结构将变化如下。

（左：初始结构；右：第 1 天。）

第三位员工可以在 3 天后领导公司。为此，只需「注销」第五位或第四位员工。如果注销第五位员工，公司的结构将变化如下。

（左：初始结构；中：第 2 天；右：第 3 天。）

第一位员工已经是公司的主管，因此对应询问的答案为 0。

第四位员工可以在两天后成为公司的主管。与上一个例子类似，只需「注销」第五位员工即可。

约束与子任务

本题的测试点分为九组。只有当该组的所有测试点以及所有所需组的测试点都通过时，该组的分数才会被计入。请注意：对某些组而言，通过样例测试并不是必需的。离线评测意味着你的程序在该组上的评测结果只有在比赛结束后才能获知。

* 某员工的「上司」是指：他的直接上司，以及他直接上司的所有上司所构成的集合。