题目描述

$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$ に複数回現れる整数があるときは、 その整数はその回数だけ使わなければならないことに注意してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ の並べ替えでなければならない。

最大のスコアを達成する方法が複数個あるときは、 そのうちのどれを出力してもよい。

题目大意

题意简述

给定一棵 $n$ 个点，$(n-1)$ 条边的无根树。树的分数定义为对于所有边，边的两个端点点权的较小值之和。
确定一个 $c_1,c_2,\cdots,c_n$ 的排列 $d_1,d_2,\cdots,d_n$，使得当点 $i$ 的点权为 $d_i$ 时，树的分数最大。要求输出最大的分数和排列 $d$。不保证 $c$ 中没有重复元素。
如果有多种方案使分数最大，输出任意一种 $d$ 即可。

输入格式

第一行 $n$，之后的 $(n-1)$ 行每行两个正整数 $a_i,b_i$，表示结点 $a_i,b_i$ 之间有连边。最后一行 $n$ 个数表示 $c_i$。

样例 #1 解释

结点 $1,2,3,4,5$ 的点权分别为 $1,2,3,4,5$，树的分数为 $1+2+3+4=10$。可以证明没有更优方案。

5
1 2
2 3
3 4
4 5
1 2 3 4 5

10
1 2 3 4 5

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

197
59 26 3141 59 53

提示

制約

• $1\ \leq\ N\ \leq\ 10000$
• $1\ \leq\ a_i,b_i\ \leq\ N$
• $1\ \leq\ c_i\ \leq\ 10^5$
• 与えられるグラフは木である

Sample Explanation 1

頂点 $1,2,3,4,5$ にそれぞれ $1,2,3,4,5$ を書き込むと、 $4$ つの辺にはそれぞれ $1,2,3,4$ が書き込まれるので、スコアは $10$ になります。 これが最大のスコアです。

Sample Explanation 2

$c_1,c_2,\ldots,c_N$ は互いに異なるとは限りません。