第 2 题拔树游戏 (`treepop`)

时间限制 1.0 s · 空间限制 256 MB · 91 个测试点 · 全文比较（过滤行末空格及文末回车）

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

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

有一棵由编号为 1 到 $N$ 的 $N$ 个节点构成的有根树。该树的根节点为 1 号节点，并且第 $i$ 号节点的父节点是第 $P_i$ 号节点（ $2 \le i \le N$ ）。此外，每个节点都有一个互不相同的整数值，第 $i$ 号节点的值为 $A_i$ （ $1 \le i \le N$ ）。

不含子节点的节点称为叶子节点。

我们从根节点（即 1 号节点）出发，每次移动到当前节点的子节点中权值最小的一个。如此重复，直到到达某个叶子节点。这样得到的从 1 号节点出发、以某个叶子节点结束的路径，记作 $S = S_1, S_2, \dots, S_k$ ，我们称其为特殊路径。

定义拔除操作如下：

设当前树的特殊路径为 $S = S_1, S_2, \dots, S_k$ 。
将 $S_1$ 与 $S_2$ 的权值交换。
将 $S_2$ 与 $S_3$ 的权值交换。
依此类推……
将 $S_{k-1}$ 与 $S_k$ 的权值交换。
从树中移除连接 $S_k$ 与其父节点之间的边。

换句话说，拔除操作会将特殊路径上的节点的权值依次向后传递，并将该路径最后一个叶子节点从树中删除。

例如，考虑下图中的树（圆圈外的数字表示节点编号，圆圈内的数字表示该节点的权值）：

在第一棵树中，特殊路径为 $S = 1, 3, 4$ ：从根节点 1 出发，子节点中权值最小的是 3 号节点，再从 3 出发，选择子节点中权值最小的 4，4 是叶子节点，结束路径。

进行拔除操作后，依次交换权值 $A_1 \leftrightarrow A_3$ ， $A_3 \leftrightarrow A_4$ ，并删除 4 与 3 之间的边，得到第二棵树。

在第二棵树中，特殊路径为 $S = 1, 2$ ：1 的子节点中权值最小的是 2，2 是叶子节点。进行拔除操作，交换 $A_1 \leftrightarrow A_2$ ，删除 2 与 1 的边，得到第三棵树。

在第三棵树中，特殊路径为 $S = 1, 3, 5$ 。拔除操作交换 $A_1 \leftrightarrow A_3$ ， $A_3 \leftrightarrow A_5$ ，然后删除 5 与 3 之间的边，得到第四棵树。

在第四棵树中，特殊路径为 $S = 1, 3$ 。执行拔除操作后交换 $A_1 \leftrightarrow A_3$ ，再删除 3 与 1 的边，得到第五棵树。

在第五棵树中，特殊路径仅为 $S = 1$ 。执行拔除操作后，直接删除根节点 1。

我们将对给定的树重复执行 $N$ 次拔除操作。请你编写一个程序，在每次拔除操作执行之前，输出当前 1 号节点的权值。

输入格式

第一行输入一个整数 $N$ ，表示节点个数。

第二行输入 $N - 1$ 个整数 $P_2, P_3, \dots, P_N$ ，表示每个节点的父节点编号，数字之间以空格分隔。

第三行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$ ，表示每个节点的初始权值，数字之间以空格分隔。

输出格式

输出共 $N$ 行，每行一个整数，第 $i$ 行表示执行第 $i$ 次拔除操作之前，1 号节点的权值。

样例

样例 1

输入：

5
1 1 3 3
5 2 1 3 4

输出：

提示

约束条件

所有给定数值均为整数。
$2 \le N \le 300\,000$
$1 \le P_i < i$ （ $2 \le i \le N$ ）
$1 \le A_i \le N$ （ $1 \le i \le N$ ）
所有 $A_i$ 两两不同。

子任务

（6 分） $N \le 3000$
（10 分）对所有 $2 \le i \le N$ ，有 $A_{P_i} < A_i$
（11 分）对所有 $2 \le i \le N$ ，有 $A_{P_i} > A_i$
（23 分）度数大于等于 3 的节点个数不超过 20
（50 分）无额外限制

翻译由 ChatGPT-4o 完成

第 2 题 拔树游戏 (treepop)