AT_ajo2024_final_e.Five Shuffles

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

有一棵包含 $N$ 个顶点的树。每个顶点编号为 $1$ 到 $N$ ，第 $i$ 条边 $(1 \leq i \leq N-1)$ 连接顶点 $u_i$ 和顶点 $v_i$ 。此外，每个顶点上写有一个 $1$ 到 $N$ 之间互不相同的整数，顶点 $i$ 上写的数是 $p_i$ 。

AtCoder 先生最多可以进行 $5$ 次如下所述的独立集洗牌操作。

独立集洗牌操作定义如下：

首先，将树的所有顶点标记为白色，然后依次执行以下两步：

选择某些顶点将其标记为黑色，但不能选择一条边连接的两个顶点都变黑；

将所有黑色顶点上的数进行任意重新排列。

进行操作后，如果能使至少 $N-2$ 个顶点满足：顶点 $i\ (1 \leq i \leq N)$ 上写的数为 $i$ ，就可以获得奖励。请给出一种实现这一目标的方法。题目保证在本问题的约束下，答案一定存在。

输入按如下格式从标准输入给出。

$N\\$
$u_1$ $v_1\\$
$u_2$ $v_2\\$
$\vdots\\$
$u_{N-1}$ $v_{N-1}\\$
$p_1$ $p_2$ $\cdots$ $p_N$

请按以下格式输出答案。

设总共做了 $K$ 次独立集洗牌（ $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

输入#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

输入#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

例如，可以像下图这样操作，在不超过 $5$ 次的独立集洗牌内达成目标。注意，不需要使所有 $N$ 个顶点都满足 $i$ 号顶点上为 $i$ 。

例如，可以像下图这样操作，在不超过 $5$ 次的独立集洗牌内达成目标。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?