[ABC348E] Minimize Sum of Distances

给出一棵 $n$ 个点的树，以及每个点的权值 $C_i$。 设 $d(u,v)$ 表示树上 $u,v$ 两点之间的距离，设 $f(x)=\sum\limits_{i=1}^n C_i\times d(x,i)$，求 $\min\limits_{1\le v\le N}f(v)$。 $1\le N\le 10^5,\space 1\le C_i\le 10^9$

[problemUrl]: https://atcoder.jp/contests/abc348/tasks/abc348_e $ N $ 頂点からなる木が与えられます。頂点は $ 1 $ から $ N $ までの番号がついており、 $ i $ 番目の辺は頂点 $ A_i,\ B_i $ を結んでいます。 長さ $ N $ の正整数列 $ C\ =\ (C_1,\ C_2,\ \ldots\ ,C_N) $ が与えられます。$ d(a,\ b) $ を頂点 $ a,\ b $ の間にある辺の数とし、 $ x\ =\ 1,\ 2,\ \ldots\ ,N $ に対して $ \displaystyle\ f(x)\ =\ \sum_{i=1}^{N}\ (C_i\ \times\ d(x,\ i)) $ とします。$ \displaystyle\ \min_{1\ \leq\ v\ \leq\ N}\ f(v) $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N\ -\ 1} $ $ B_{N\ -\ 1} $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_N $

答えを一行に出力せよ。

4
1 2
1 3
2 4
1 1 1 2

5

2
2 1
1 1000000000

1

7
7 3
2 5
2 4
3 1
3 6
2 1
2 7 6 9 3 4 6

56

### 制約 - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ - 与えられるグラフは木である。 - $ 1\ \leq\ C_i\ \leq\ 10^9 $ ### Sample Explanation 1 例として、 $ f(1) $ を求めることを考えます。$ d(1,\ 1)\ =\ 0,\ d(1,\ 2)\ =\ 1,\ d(1,\ 3)\ =\ 1,\ d(1,\ 4)\ =\ 2 $ です。 よって、 $ f(1)\ =\ 0\ \times\ 1\ +\ 1\ \times\ 1\ +\ 1\ \times\ 1\ +\ 2\ \times\ 2\ =\ 6 $ となります。 同様に、 $ f(2)\ =\ 5,\ f(3)\ =\ 9,\ f(4)\ =\ 6 $ です。$ f(2) $ が最小なので `5` を出力します。 ### Sample Explanation 2 $ f(2)\ =\ 1 $ で、これが最小です。