树

题目描述:

兔警官朱迪不但聪明能干，而且特别勤奋好学。她常常利用工作闲暇之余研究信奥中的难题。

她有一棵由编号为$1~n$的 $n$个节点构成的有根树。该树的根节点为$1$号节点，并且第$i(2 \le i \le n)$号节点的父节点是第$p_i$号节点。此外，每个节点都有一个互不相同的整数权值，第 $i( 1 \le i \le n)$号节点的权值为 $a_i( 1 \le i \le n)$，所有$a_i$两两各不相同。

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

我们从根节点(即$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$出发，  $1$的子节点中权值最小的是$3$号节点，再从$3$号节点出发，选择子节点中权值最小的$4$号节点，$4$号节点是叶子节点，结束路径。执行移除操作，依次交换权值 $a_1 \leftrightarrow a_3$， $a_3 \leftrightarrow a_4$，并删除节点$4$与 $3$之间的边，得到第二棵树。

在第二棵树中，特殊路径为$S={1,2}$。从根节点$1$出发， $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$，其中$P_i$表示节点$i( 2 \le i \le n)$的父节点编号。

第三行包含$n$个整数 $a_1,a_2, \dots, a_n$，其中$a_i$表示节点$i( 1 \le i \le n)$的初始权值，所有a_i两两各不相同。

输出格式:

输出共 $n$行，每行一个整数。第 $i( 1 \le i \le n)$行表示执行第$i$次移除操作之前，  $1$号节点的权值。

数据范围:

对于100%的数据：$ 2 \le n \le 300,000； 1 \le p_i \le n ( p_i \ne i, 2 \le i \le n)；1 \le a_i \le n( 1 \le i \le n)$。

测试点编号	特殊限制
1~3	$2 \le n \le 3000$
4	$p_i = i-1( 2 \le i \le n)$
5~6	$a_{pi} \lt a_i( 2 \le i \le n )$
7~9	$a_{pi} \gt a_i( 2 \le i \le n )$
10~12	度数大于等于$3$的节点个数不超过$20$
13~20	无特殊限制

样例输入:

(双击复制)

样例1：
5
1 1 3 3
5 2 1 3 4

样例2：
14
10 1 10 3 3 14 1 10 3 4 4 5 1
6 10 5 9 7 14 13 12 3 4 1 8 2 11

样例输出:

(双击复制)

样例1：
5
1
2
3
4

样例2：
6
5
4
3
7
2
9
1
8
10
11
12
13
14

提示:

【样例2解释】

图中圆圈外的数字表示节点编号，圆圈内的数字表示该节点的权值。该图展示了第 $1$次移除操作时的特殊路径 $S={1,3,10,9}$，如上图中的红色路线。

时间限制: 1000ms
空间限制: 256MB

---

来源: 26年比赛初中组t5