← 返回题目列表

AtCoder · arc156_c

C. 树和 LCS

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

分数: 600 点

问题陈述

我们有一棵树 T 顶点编号 1 to N。的 i第一个边缘 T 连接顶点 u_i 和顶点 v_i.

让我们使用 T 定义 相似度 的排列 P = (P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) 如下。

  • 对于简单路径 x=(x_1,x_2,\ldots,x_k) in T,让 y=(P_{x_1}, P_{x_2},\ldots,P_{x_k})。相似度是最长公共子序列的最大可能长度 x 和 y.

构造一个排列 P 相似度最小。

什么是子序列? 序列的 A 子序列 长度为 $$$m$$$ 的 是通过从该序列中删除零个或多个元素并在不改变相对顺序的情况下连接剩余元素而获得的序列。 例如, (10,30) 是以下序列的子序列 (10,20,30),但是 (20,10) 不是。
什么是简单路径? 对于顶点 图表中的 X 和 Y 在图表中 G,一个 步行 来自 X to Y 是一系列顶点 v_1,v_2, \ldots, v_k 这样 v_1=X, v_k=Y,并且有一条边连接 v_i 和 v_{i+1}。一个 简单路径 (或者只是一个 路径) 是这样的步行 v_1,v_2, \ldots, v_k 都是不同的。

约束

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

输入

输入由标准输入按以下格式给出:

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

输出

打印排列 P 相似度最小,用空格分隔。如果存在多个解决方案,您可以打印其中任何一个。


示例输入 1

3
1 2
2 3

示例输出 1

3 2 1

这个排列有以下相似之处: 1,可以如下计算。

  • 对于 x=(1),我们有 y=(P_1)=(3)。的最长公共子序列的长度 x 和 y is 0.

  • 对于 x=(2),我们有 y=(P_2)=(2)。的最长公共子序列的长度 x 和 y is 1.

  • 对于 x=(3),我们有 y=(P_2)=(1)。的最长公共子序列的长度 x 和 y is 0.

  • 对于 x=(1,2),我们有 y=(P_1,P_2)=(3,2)。的最长公共子序列的长度 x 和 y is 1。同样适用于 x=(2,1),反转 (1,2).

  • 对于 x=(2,3),我们有 y=(P_2,P_3)=(2,1)。的最长公共子序列的长度 x 和 y is 1。同样适用于 x=(3,2),反转 (2,3).

  • 对于 x=(1,2,3),我们有 y=(P_1,P_2,P_3)=(3,2,1)。的最长公共子序列的长度 x 和 y is 1。同样适用于 x=(3,2,1),反转 (1,2,3).

我们可以证明没有排列具有以下相似度 0 或更少,所以这个排列是一个有效的答案。


示例输入 2

4
2 1
2 3
2 4

示例输出 2

3 4 1 2

如果多个排列具有最小相似度,则可以打印其中任何一个。例如,您还可以打印 4 3 2 1.