题目描述

强哥的装甲师正在守卫 Moskva。由于 Gordon 的大军正在同时进攻 Moskva 外围的 $n$ 个据点，所以强哥不得不将他的师分散进行防守，编号为 $i$ 的据点里面现在有强哥的 $C_i$ 辆坦克。

现在，史黛琳让强哥的装甲师选择去其中的一个据点集中，并从那里开始反击。

坦克们自然需要移动，但是移动需要花费燃油。一辆坦克移动 $1$ 距离需要花费 $1$ 点燃油。

强哥手里有外围的 $n$ 个据点的地图，且这个地图上总共有 $n-1$ 条双向道路连接这些据点，道路的长度都是 $1$。

强哥手里的燃油储备不多了，他想知道执行这次命令最少需要花费多少燃油，并做好找史黛琳要油的准备。

输入格式

总共 $n+1$ 行。第一行为一个数 $n$，然后 $n+1$ 行每一行代表一条双向道路，最后一行有 $n$ 个数，其中第 $i$ 个数是 $C_i$。

输出格式

只有一个数，为消耗燃油总量的最小值。

4
1 2
1 3
2 4
1 1 1 2

5

2
2 1
1 1000000000

1

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

56

数据范围

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ C_i\ \leq\ 10^9$