← 返回题目列表

AtCoder · ajo2024_final_e

E. 五次洗牌

中文机器翻译题面 查看原题

配点 : 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。

  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