AT_arc156_c.[ARC156C] Tree and LCS

有一棵编号为 $1$ 到 $N$ 的树 $T$。$T$ 的第 $i$ 条边（$1\leq i\leq N-1$）连接了顶点 $u_i$ 和顶点 $v_i$。

利用 $T$，我们定义排列 $P=(P_1,P_2,\ldots,P_N)$（$1$ 到 $N$ 的一个排列）的相似度如下：

• 对于 $T$ 上任意的简单路径 $x=(x_1,x_2,\ldots,x_k)$，令 $y=(P_{x_1},P_{x_2},\ldots,P_{x_k})$。此时，$x$ 和 $y$ 的最长公共子序列的最大长度即为相似度。

请构造一个使相似度最小的排列 $P$。

子序列的定义
数列的子序列是指从数列中删除 $0$ 个或多个元素后，按原顺序连接剩下元素得到的数列。例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，但 $(20,10)$ 不是 $(10,20,30)$ 的子序列。

简单路径的定义
在图 $G$ 上，顶点 $X,Y$ 间的顶点序列 $v_1,v_2,\ldots,v_k$，满足 $v_1=X$，$v_k=Y$，且对于 $1\leq i\leq k-1$，$v_i$ 和 $v_{i+1}$ 有边相连，这样的序列称为从 $X$ 到 $Y$ 的步行。如果 $v_1,v_2,\ldots,v_k$ 均互不相同，则称为从 $X$ 到 $Y$ 的简单路径（或简称路径）。

输入通过标准输入给出，格式如下：

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

请输出一个使相似度最小的排列 $P$，用空格分隔。如果有多个解，输出任意一个均可。

限制条件

• $2\leq N\leq 5000$
• $1\leq u_i,v_i\leq N$
• 给定的图一定是一棵树
• 输入的所有数均为整数

样例解释 1

输出样例中的排列的相似度为 $1$。具体计算如下：

• 当 $x=(1)$ 时，$y=(P_1)=(3)$，$x$ 和 $y$ 的最长公共子序列长度为 $0$。
• 当 $x=(2)$ 时，$y=(P_2)=(2)$，$x$ 和 $y$ 的最长公共子序列长度为 $1$。
• 当 $x=(3)$ 时，$y=(P_3)=(1)$，$x$ 和 $y$ 的最长公共子序列长度为 $0$。
• 当 $x=(1,2)$ 时，$y=(P_1,P_2)=(3,2)$，$x$ 和 $y$ 的最长公共子序列长度为 $1$。对于反向的 $x=(2,1)$ 也同理。
• 当 $x=(2,3)$ 时，$y=(P_2,P_3)=(2,1)$，$x$ 和 $y$ 的最长公共子序列长度为 $1$。对于反向的 $x=(3,2)$ 也同理。
• 当 $x=(1,2,3)$ 时，$y=(P_1,P_2,P_3)=(3,2,1)$，$x$ 和 $y$ 的最长公共子序列长度为 $1$。对于反向的 $x=(3,2,1)$ 也同理。

可以证明不存在相似度小于等于 $0$ 的排列，因此这就是答案。

样例解释 2

当存在多个使相似度最小的排列时，输出任意一个均可。例如，4 3 2 1 这样的输出也是正确答案。

由 ChatGPT 4.1 翻译