← 返回题目列表

AtCoder · abc348_e

H. 最小化距离总和

中文机器翻译题面 查看原题

分数: 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