[ABC348] E - Minimize Sum of Distances

E - Minimize Sum of Distances

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 475 分

题面

给定一个包含 个顶点的树。顶点编号为 到 ，第 条边连接顶点 和 。

同时给定一个长度为 的正整数序列 。定义 为顶点 和顶点 之间的边数，对于 ，令 。求 。

限制条件

• 给定图是一棵树。

---

输入

从标准输入获得输入，格式如下：

输出

在一行中输出答案。

---

输入样例 1

4
1 2
1 3
2 4
1 1 1 2

输出样例 1

5

例如，考虑计算 。我们有 。
因此，。

类似地，。由于 是最小的，输出 5。

---

输入样例 2

2
2 1
1 1000000000

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