AT_m_solutions2019_d Maximum Sum of Minimum

给定一棵包含 $N$ 个顶点 $1,2,\ldots,N$ 的树 $T$，以及一组正整数 $c_1,c_2,\ldots,c_N$。第 $i$ 条边（$1 \leq i \leq N-1$）连接顶点 $a_i$ 和顶点 $b_i$。 在 $T$ 的每个顶点上写入一个正整数后，按照如下方式计算分数： - 对于每条边，将其两个端点上写入的整数中较小的一个写在该边上。 - 所有边上写入的整数之和即为分数。 请你求出将 $c_1,c_2,\ldots,c_N$ 分别写入每个顶点（每个数只能用一次，若有重复则必须用对应次数）时，能够获得的最大分数，并构造一种达到该最大分数的写法。 注意，如果 $c_1,c_2,\ldots,c_N$ 中有重复的整数，则每个整数必须使用对应的次数。

输入以如下格式从标准输入读入。 > $N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $\ldots$ $c_N$

请按如下格式输出。 > $M$ $d_1$ $\ldots$ $d_N$ $M$ 表示最大分数。$d_i$ 表示应写在顶点 $i$ 上的整数。$d_1,d_2,\ldots,d_N$ 必须是 $c_1,c_2,\ldots,c_N$ 的一个排列。 如果有多种达到最大分数的方法，输出其中任意一种即可。

### 限制条件 - $1 \leq N \leq 10000$ - $1 \leq a_i, b_i \leq N$ - $1 \leq c_i \leq 10^5$ - 给定的图一定是一棵树 ### 样例解释 1 将 $1,2,3,4,5$ 分别写在顶点 $1,2,3,4,5$ 上时，$4$ 条边上分别写入 $1,2,3,4$，因此分数为 $10$。这是最大分数。 ### 样例解释 2 $c_1,c_2,\ldots,c_N$ 不一定互不相同。 由 ChatGPT 4.1 翻译