这个问题分为两个任务。在此任务中,您需要找到最小可能的答案。在村庄(最大)任务中,您需要找到最大可能的答案。每项任务价值 $$$50$$$ 积分。
某个村庄有$$$N$$$间房屋。每栋房子里都住着一个村民。这些房屋由道路相连。每条路连接两栋房屋,长度正好 $$$1$$$ 公里。从每栋房屋都可以通过一条或多条连续的道路到达任何其他房屋。村里总共有$$$N-1$$$条道路。
有一天,所有村民决定搬到不同的房子里——也就是说,搬家后,每栋房子里应该再有一个村民住在里面,但不能有村民像以前一样住在同一栋房子里。我们想知道所有村民的新旧房屋之间的最短路径的最小可能总长度(以公里为单位)。
有七间房屋的村庄示例
例如,如图所示,如果有七栋房屋通过道路连接,则最小总长度为 $$$8$$$ 公里(这可以通过将 $$$1 \to 6$$$、$$$2 \to 4$$$、$$$3 \to 1$$$、$$$4 \to 2$$$、$$$5 \to 7$$$、$$$6 \to 来实现3$$$、$$$7 \ 到 5$$$)。
编写一个程序,找出最短路径的最小总长度(以公里为单位),并举例将新房屋分配给村民。
输入
第一行包含一个整数 $$$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
4 2 1 4 3
输入 #2
7 4 2 5 7 3 4 6 3 1 3 4 5
输出 #2
8 3 4 6 2 7 1 5
注意
评分:
子任务:
1.(6 分)$$$N \leq 10$$$
2. (19 点) $$$N \leq 1\,000$$$
3.(25分)没有进一步的限制