题目描述

薯条哥拿到了一棵树，$i$号节点上有一个种类为$j$的货物。现在薯条哥需要将相同种类的货物搬运到同一个节点。已知搬运一个种类为$z$的货物每走一步的消耗为$z$，现在薯条哥希望你帮他求出最小的总消耗，你能帮帮他吗?

输入描述

第一行输入一个正整数$n(1\le n\le 10^5)$代表树的节点数量。

接下来的$n- 1$行，每行输入两个正整数$u,v(1\le u,v\le n)$，代表节点$u$和节点$v$有一条边连接。

接下来的一行输入$n$个正整数$a_i(1\le a_i\le 10)$，代表每个节点上的货物种类。

输出描述

输出一个整数，代表消耗的最小值。

样例1

输入

4
1 2
1 3
2 4
1 1 1 2

输出

2

样例2

输入

5
1 2
3 4
3 2
5 1
9 6 4 3 2

输出

0