E - Minimize Sum of Distances Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

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) を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは木である。
  • 1 \leq C_i \leq 10^9

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}
C_1 C_2 \cdots C_N

出力

答えを一行に出力せよ。

入力例 1

4
1 2
1 3
2 4
1 1 1 2

出力例 1

5

例として、 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 を出力します。

入力例 2

2
2 1
1 1000000000

出力例 2

1

f(2) = 1 で、これが最小です。

入力例 3

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

出力例 3

56

Score: 475 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.

You are also given a sequence of positive integers C = (C_1, C_2, \ldots ,C_N) of length N. Let d(a, b) be the number of edges between vertices a and b, and for x = 1, 2, \ldots, N, let \displaystyle f(x) = \sum_{i=1}^{N} (C_i \times d(x, i)). Find \displaystyle \min_{1 \leq v \leq N} f(v).

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is a tree.
  • 1 \leq C_i \leq 10^9

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}
C_1 C_2 \cdots C_N

Output

Print the answer in one line.

Sample Input 1

4
1 2
1 3
2 4
1 1 1 2

Sample Output 1

5

For example, consider calculating f(1). We have d(1, 1) = 0, d(1, 2) = 1, d(1, 3) = 1, d(1, 4) = 2.
Thus, f(1) = 0 \times 1 + 1 \times 1 + 1 \times 1 + 2 \times 2 = 6.

Similarly, f(2) = 5, f(3) = 9, f(4) = 6. Since f(2) is the minimum, print 5.

Sample Input 2

2
2 1
1 1000000000

Sample Output 2

1

f(2) = 1, which is the minimum.

Sample Input 3

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

Sample Output 3

56