配点 : 1300 点
問題文
N 顶点的树。顶点有编号,直到 1 减去 N 。i 号边 (1 \leq i \leq N-1) 是边 u_i 和边 v_i 相连。 此外,每个顶点上 1 以上 N 以下写有不同的整数,边 i (1 \leq i \leq N) 上写的整数是 p_i 。
AtCoder 能够,以下独立集合 shaffuru最多 5 次进行。
独立集合shaffuruto是
将树的每个顶点涂成白色后,按顺序执行下面的步骤 1 和 2。
- 将树的一些顶点涂成黑色。然而,相邻的边缘 2 不要将两个顶点都涂成黑色。
- 对写在黑色顶点处的整数进行排序。
操作后,至少 对于 N-2 顶点,顶点 i (1 \leq i \leq N) 中写入的整数 如果你能做到 i ,你就会得到钱。 这样的方法 1 请找到一个。 然而,在这个问题的约束下,可以证明总有答案。
制約
- 3 \leq N \leq 150\,000
- 1 \leq u_i < v_i \leq N
- 1 \leq p_i \leq N
- p_1, p_2, \dots, p_N 都不同
- 作为输入给出的图是一棵树
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
p_1 p_2 \cdots p_N
出力
请按以下格式输出您的答案。
然而,要执行的独立集洗牌次数为 K (\leq 5)、i 独立集洗牌后立即的顶点 比方说 j 中写入的整数 如果你能做到 a_{i,j} 。 在这里,无需最小化操作次数。
K
a_{1,1} a_{1,2} \cdots a_{1,N}
a_{2,1} a_{2,2} \cdots a_{2,N}
\vdots
a_{K,1} a_{K,2} \cdots a_{K,N}
入力例 1
6 1 2 1 3 2 4 2 5 3 6 3 1 5 6 4 2
出力例 1
2 2 1 5 3 4 6 2 1 3 4 5 6
例如,如果您按如下所示操作, 您只需进行不超过5 组独立洗牌即可实现您的目标。 此外,N 所有顶点的顶点 请注意,它不一定是 i 中写入的整数 如果你能做到 i 。 您只需进行不超过

入力例 2
6 1 2 2 3 3 4 4 5 5 6 6 3 5 1 4 2
出力例 2
4 1 3 5 2 4 6 1 4 5 2 3 6 1 2 5 4 3 6 1 2 3 4 5 6
例如,如果您按如下所示操作, 您只需进行不超过5 组独立洗牌即可实现您的目标。

入力例 3
10 1 2 1 3 2 4 2 5 4 6 3 7 1 8 1 9 2 10 1 2 3 4 5 6 8 7 9 10
出力例 3
0