AT_abc348_e [ABC348E] Minimize Sum of Distances

题目描述

给定一棵包含 $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$，定义

$$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$

输出格式

请输出一个整数，表示答案。

输入输出样例 #1

输入 #1

4
1 2
1 3
2 4
1 1 1 2

输出 #1

5

输入输出样例 #2

输入 #2

2
2 1
1 1000000000

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

56

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• 给定的图是一棵树。
• $1 \leq C_i \leq 10^9$

样例解释 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。

样例解释 2

$f(2) = 1$，这是最小值。

由 ChatGPT 4.1 翻译