You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC348E] Minimize Sum of Distances

题目描述

给定一棵 $N$ 个顶点的树，每个点有一个点权 $C_i$。定义 $d(a,b)$ 表示 $a$ 和 $b$ 之间的简单路径的边数（即距离），定义 $\displaystyle\ f(x)\ =\ \sum_{i=1}^{N}\ (C_i\ \times\ d(x,\ i))$ ，求 $\displaystyle\ \min_{1\ \leq\ v\ \leq\ N}\ f(v)$ 。

输入格式

第一行一个整数 $N$ ，接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 表示树边，最后一行 $N$ 个整数 $C_i$ 表示点权。

输出格式

一个整数表示答案。

输入输出样例 #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$