分数: 500 点
问题陈述
你有一棵树 N 顶点 1,2,\ldots,N和正整数 c_1,c_2,\ldots,c_N。 的 i树中的第一条边 (1 \leq i \leq N-1) 连接顶点 a_i 和顶点 b_i.
我们将在每个顶点上写一个正整数 T 并计算我们的 分数 $$$v$$$ 的 如下:
- 在每个边上,写入两个端点上写入的整数中较小的一个。
- 让我们的分数为所有边上写入的整数的总和。
当我们写下每个时,找到最大可能的分数 c_1,c_2,\ldots,c_N 在一个顶点上 T,并展示一种实现它的方法。如果一个整数出现多次 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
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
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 是要写入 Vertex 的整数 i. d_1,d_2,\ldots,d_N 必须是以下排列 c_1,c_2,\ldots,c_N。 如果有多种方法可以达到最高分,则任何一种方法都将被接受。 顶点上的
样本输入 1
5 1 2 2 3 3 4 4 5 1 2 3 4 5
示例输出 1
10 1 2 3 4 5
如果我们写 1,2,3,4,5 在顶点上 1,2,3,4,5分别写在四个边上的整数将是 1,2,3,4,得分为 10。这是可能的最高分数。
示例输入 2
5 1 2 1 3 1 4 1 5 3141 59 26 53 59
示例输出 2
197 59 26 3141 59 53
c_1,c_2,\ldots,c_N 可能不成对不同。