最小化距离之和

题目描述

给定一棵有 $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) ]

求

[ \min_{1 \le v \le 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$

输出格式

在一行内输出答案。

样例

4
1 2
1 3
2 4
1 1 1 2

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

1

$f(2) = 1$,为最小值。

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

56

数据范围

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