← 返回题目列表

AtCoder · m_solutions2019_d

D. 最小值的最大总和

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

分数: 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 可能不成对不同。