103484: [Atcoder]ABC348 E - Minimize Sum of Distances

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

问题描述

你被给定一棵有 $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