E - Minimize Sum of Distances

コンテスト時間: 2024-04-06(土) 12:00 ~ 2024-04-06(土) 13:40 (100分) AtCoderホームへ戻る

E - Minimize Sum of Distances 解説

実行時間制限: 2 sec / メモリ制限: 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$

出力

答えを一行に出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

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

入力例 2Copy

Copy

2
2 1
1 1000000000

出力例 2Copy

Copy

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

入力例 3Copy

Copy

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

出力例 3Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

2
2 1
1 1000000000

Sample Output 2Copy

Copy

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

Sample Input 3Copy

Copy

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

Sample Output 3Copy

Copy