/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
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 の各頂点に正の整数を書き込んだとき、以下のようにしてスコアを計算します。
- 各辺に、2 つの端点に書き込まれた整数のうち小さい方を書き込む。
- 各辺に書き込まれた整数の総和をスコアとする。
T の各頂点に c_1,c_2,\ldots,c_N を 1 つずつ書き込んだときのスコアの最大値を求め、 それを達成する正の整数の書き込み方を 1 つ構成してください。
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 は頂点 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 を書き込むと、 4 つの辺にはそれぞれ 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 は互いに異なるとは限りません。
Score : 500 points
Problem Statement
You are given a tree with N vertices 1,2,\ldots,N, and positive integers c_1,c_2,\ldots,c_N. The i-th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i.
We will write a positive integer on each vertex in T and calculate our score as follows:
- On each edge, write the smaller of the integers written on the two endpoints.
- Let our score be the sum of the integers written on all the edges.
Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T, and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N, we must use it that number of times.
Constraints
- 1 \leq N \leq 10000
- 1 \leq a_i,b_i \leq N
- 1 \leq c_i \leq 10^5
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N
Output
Use the following format:
M d_1 \ldots d_N
where M is the maximum possible score, and d_i is the integer to write on Vertex i. d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N. If there are multiple ways to achieve the maximum score, any of them will be accepted.
Sample Input 1
5 1 2 2 3 3 4 4 5 1 2 3 4 5
Sample Output 1
10 1 2 3 4 5
If we write 1,2,3,4,5 on Vertex 1,2,3,4,5, respectively, the integers written on the four edges will be 1,2,3,4, for the score of 10. This is the maximum possible score.
Sample Input 2
5 1 2 1 3 1 4 1 5 3141 59 26 53 59
Sample Output 2
197 59 26 3141 59 53
c_1,c_2,\ldots,c_N may not be pairwise distinct.