[ABC359] G - Sum of Tree Distance

G - Sum of Tree Distance

Time Limit: 4 sec / Memory Limit: 1024 MB

分数: 600 分

题面

给定一棵有 个顶点的树。第 条边双向连接顶点 和 。

此外，给定一个整数序列 。

在此，定义 如下:

• 若 ，则 是从顶点 移动到顶点 需要穿过的最小边数。若 ，则 。

计算以下表达式的值:

。

限制条件

• 输入的图是一棵树。
• 所有输入值均为整数。

---

输入

从标准输入中以以下格式给出：

输出

输出答案。

---

输入样例 1

4
3 4
4 2
1 2
2 1 1 2

输出样例 1

4

。对于所有其他 ，我们有 ，因此答案为 。

---

输入样例 2

8
8 6
3 8
1 4
7 8
4 5
3 4
8 2
1 2 2 2 3 1 1 3

输出样例 2

19