AT_m_solutions2019_d Maximum Sum of Minimum

[problemUrl]: https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d $ 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 $ の並べ替えでなければならない。 最大のスコアを達成する方法が複数個あるときは、 そのうちのどれを出力してもよい。

### 制約 - $ 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 $ は互いに異なるとは限りません。