分数: 475 点
问题陈述
你有一棵树 N 顶点。顶点已编号 1 to N,以及 i第一条边连接顶点 A_i 和 B_i.
还给你一个正整数序列 C = (C_1, C_2, \ldots ,C_N) 长度 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