Village (Minimum)

题意翻译

### 题意 [最大值版本](https://www.luogu.com.cn/problem/CF1387B2) 村里 $n$ 个房子构成了一个 $n$ 点 $n-1$ 条边的**树**结构（下标从 $1$ 开始），每条边长度均为 $1$。一开始每个房子里分别有一个村民。 现在所有村民都需要搬家（改变自己所在的点），搬家后依然需要满足每个房子里**有且只有一个**村民。也就是说，如果原本位于点 $i$ 的村民搬到了点 $v_i$，那么应当满足： - 对于任意点 $i$，有 $i \neq v_i$。 - 对于任意两个不同的点 $i$ 与 $j$，有 $v_i \neq v_j$。 村民 $i$ 搬家的花费是点 $i$ 到点 $v_i$ 的树上距离（即树上二点间相隔的边数），总花费为所有村民花费之和。求总花费的**最小值**及其方案。 ### 输入格式 第一行一个正整数 $n$，表示树的点数。 接下来 $n-1$ 行每行二整数 $a$ 和 $b$，表示树上有一条连接 $a$ 和 $b$，长度为 $1$ 的边。 ### 输出格式 第一行一个整数，表示总花费的**最小值**。 第二行 $n$ 个整数 $v_1 \dots v_n$，表示搬家的方案：如果原本位于点 $i$ 的村民搬到了点 $v_i$。 输出**任意一组**合法方案即可。 ### 数据范围 - $2 \leq n \leq 10^5$ - $1 \leq a,b \leq n$

题目描述

This problem is split into two tasks. In this task, you are required to find the minimum possible answer. In the task Village (Maximum) you are required to find the maximum possible answer. Each task is worth $ 50 $ points. There are $ N $ houses in a certain village. A single villager lives in each of the houses. The houses are connected by roads. Each road connects two houses and is exactly $ 1 $ kilometer long. From each house it is possible to reach any other using one or several consecutive roads. In total there are $ N-1 $ roads in the village. One day all villagers decided to move to different houses — that is, after moving each house should again have a single villager living in it, but no villager should be living in the same house as before. We would like to know the smallest possible total length in kilometers of the shortest paths between the old and the new houses for all villagers. Example village with seven houses For example, if there are seven houses connected by roads as shown on the figure, the smallest total length is $ 8 $ km (this can be achieved by moving $ 1 \to 6 $ , $ 2 \to 4 $ , $ 3 \to 1 $ , $ 4 \to 2 $ , $ 5 \to 7 $ , $ 6 \to 3 $ , $ 7 \to 5 $ ). Write a program that finds the smallest total length of the shortest paths in kilometers and an example assignment of the new houses to the villagers.

输入输出格式

输入格式

The first line contains an integer $ N $ ( $ 1 < N \le 10^5 $ ). Houses are numbered by consecutive integers $ 1, 2, \ldots, N $ . Then $ N-1 $ lines follow that describe the roads. Each line contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le N $ , $ a \neq b $ ) denoting that there is a road connecting houses $ a $ and $ b $ .

输出格式

In the first line output the smallest total length of the shortest paths in kilometers. In the second line describe one valid assignment of the new houses with the smallest total length: $ N $ space-separated distinct integers $ v_1, v_2, \ldots, v_N $ . For each $ i $ , $ v_i $ is the house number where the villager from the house $ i $ should move ( $ v_i \neq i $ ). If there are several valid assignments, output any of those. Scoring Subtasks: 1. (6 points) $ N \leq 10 $ 2. (19 points) $ N \leq 1\,000 $ 3. (25 points) No further constraints

输入输出样例

输入样例 #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