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 翻译