← 返回题目列表

Codeforces · 1387/B2

B2. 村庄(最大)

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

这个问题分为两个任务。在这个任务中,你需要找到最大可能的答案。在村庄(最小)任务中,您需要找到最小可能的答案。每项任务价值 $$$50$$$ 积分。

某个村庄有$$$N$$$间房屋。每栋房子里都住着一个村民。这些房屋由道路相连。每条路连接两栋房屋,长度正好 $$$1$$$ 公里。从每栋房屋都可以通过一条或多条连续的道路到达任何其他房屋。村里总共有$$$N-1$$$条道路。

有一天,所有村民决定搬到不同的房子里——也就是说,搬家后,每栋房子里应该再有一个村民住在里面,但不能有村民像以前一样住在同一栋房子里。我们想知道所有村民的新旧房屋之间的最短路径的最大可能总长度(以公里为单位)。

有七间房屋的村庄示例

例如,如图所示,如果有七栋房屋通过道路连接,则最大总长度为 $$$18$$$ 公里(可以通过将 $$$1 \to 7$$$、$$$2 \to 3$$$、$$$3 \to 4$$$、$$$4 \to 1$$$、$$$5 \to 2$$$、$$$6 \to 来实现5$$$、$$$7 \ 到 6$$$)。

编写一个程序,找出最短路径的最大总长度(以公里为单位),并举例将新房屋分配给村民。

输入

第一行包含一个整数 $$$N$$$ ($$$1 < N \le 10^5$$$)。房屋由连续整数 $$$1, 2, \ldots, N$$$ 编号。

然后 $$$N-1$$$ 行描述道路。每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le N$$$, $$$a \neq b$$$) 表示有一条路连接房屋 $$$a$$$ 和 $$$b$$$。

输出

在第一行中输出最短路径的最大总长度(以公里为单位)。

在第二行中,描述了总长度最大的新房屋的一个有效分配: $$$N$$$ 空格分隔的不同整数 $$$v_1, v_2, \ldots, v_N$$$。对于每个 $$$i$$$,$$$v_i$$$ 是 $$$i$$$ 房屋的村民应移动的房屋号码 ($$$v_i \neq i$$$)。如果有多个有效分配,则输出其中任何一个。

示例

输入 #1

4
1 2
2 3
3 4

输出 #1

8
4 3 2 1

输入 #2

7
4 2
5 7
3 4
6 3
1 3
4 5

输出 #2

18
2 7 4 1 3 5 6

注意

评分:
子任务:

1.(6 分)$$$N \leq 10$$$
2. (19 分) $$$N \leq 1\,000$$$
3.(25分)没有进一步的限制