P12075 [OOI 2025] Dreaming is not harmful

[试题来源](https://inf-open.ru/2024-25/final-materials/)。

在婚礼策划公司 M.，计划进行大规模裁员。所有员工都在忙着计算天数，期待着在有利的情况下，他们能够取代现有的领导，执掌公司。 公司的结构表示为一个以顶点 $1$ 为根的悬挂树。员工编号 $v$ 的直接主管是编号为 $p_v$ 的员工。员工 $v$ 的能力水平由参数 $s_v$ 定义。这个参数是所有员工的独立值，且能力水平越高，员工对公司越有用。注意，由于不透明的招聘过程，可能会出现能力较低的员工是能力较高员工的主管的情况。 由于公司进行大规模人员调整，每天位于工作层级结构根部的 CEO 会被解雇。如果公司中还有员工，则能力最强的直接下属会接替 CEO 的位置。之后，前任主管的其他下属将成为新任主管的下属。为了更好地理解这个条件，可以参考样例中的说明。 每个员工都轻松地计算出自己成为 CEO 需要多少天。许多人不愿意等那么久，因为他们只能当一天的主管！为了加速这个过程，他们准备“拉黑”（cancel）一位同事。被“拉黑”的员工的能力水平会降至 $0$，因为没有人再愿意与他们互动。 您需要回答 $q$ 个询问。在第 $k$ 个询问中，编号为 $v_k$ 的员工想知道，如果他们愿意“拉黑”**恰好**一名员工，他们能够领导公司的最少等待天数是多少。所有询问都是假想且独立的，员工的实际能力水平在所有询问中保持不变。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 300\,000$，$1 \le q \le n$）—— 员工数量和询问数量。 第二行包含 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i < i$）—— 编号从 $2$ 到 $n$ 的员工的直接主管。 第三行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \le s_i \le n$）—— 员工的能力水平。保证它们都是不同的。 第四行包含 $q$ 个整数 $v_1, v_2, \dots, v_q$（$1 \le v_i \le n$）—— 晋升询问。保证所有数字 $v_i$ 都是不同的。

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

**样例解释** 在测试样例中，第五名员工可以在 1 天后领导公司。为此，只需“拉黑”第二名员工即可。公司结构将如下改变：  第三名员工可以在 3 天后领导公司。为此，只需“拉黑”第五名或第四名员工即可。如果拉黑第五名员工，公司结构将如下改变：  第一名员工已经是公司的领导者，因此对应查询的答案是 $0$。 第四名员工可以在两天后成为公司领导。与前一个例子类似，只需“拉黑”第五名员工即可。 **评分** 本题的测试点包含九个分组。每个分组的分数只有在该分组的所有测试点以及所有依赖分组的测试点都通过时才能获得。请注意，通过样例测试点对于某些分组不是必需的。$\textbf{Offline-evaluation}$ 表示该分组的测试结果将在比赛结束后才可查看。 | Subtask | 分数 | 额外限制：$n$ | 额外限制：$q$ | 依赖组别 | 说明 | | :--- | :--- | :---------- | :---------- | :------- | :-------------------------------------------------------------------- | | 0 | 0 | -- | -- | -- | 样例。 | | 1 | 10 | -- | -- | -- | $p_i = 1$ 或 $p_i = i - 1$，其中 $p_i = 1$ 的 $i$ 不超过两个。 | | 2 | 6 | -- | -- | 1 | $p_i = 1$ 或 $p_i = i - 1$。 | | 3 | 8 | $n \le 50$ | $q \le 50$ | 0 | | | 4 | 13 | $n \le 1000$ | $q \le 1000$ | 0, 3 | | | 5 | 11 | -- | $q \le 100$ | 0, 3 | | | 6 | 9 | -- | -- | -- | $p_i = \lfloor \frac{i}{2} \rfloor$。 | | 7 | 11 | -- | -- | 0, 3, 6 | 任何员工的主管\*数量不超过 $100$。 | | 8 | 14 | -- | -- | -- | $s_i > s_{p_i}$ 对于任何 $i > 1$。 | | 9 | 18 | -- | -- | 0 -- 8 | **Offline-evaluation.** | 主管\*：直接或者间接的主管。