AT_abc348_e [ABC348E] Minimize Sum of Distances

[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

N/A

### 制約 - $ 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 $ で、これが最小です。