阿畅在游戏《DOTA2》里最喜欢的英雄是鱼人守卫。每一天，他都要使用这个英雄，在游戏地图的河道里冲刺来冲刺去。 《DOTA2》的河道是一棵拥有 n 个结点的树。在每一个结点，都会生成一个赏金神符。当阿畅来到这个结点后，他就可以收起神符，等回到泉水后激活，为他的队伍提供经济支持。每一个结点的赏金神符会为他的队伍提供特定数额的金钱，它们可能相同，也可能不同。 但是，阿畅的背包是有容量限制的，在同一时间只能承载一个赏金神符。所以，阿畅制定了这样的策略：他会选择两个不同的结点 u,v ，在两个结点之间的最短路上进行冲刺。在一次行进过程中，他只会捡拾所经过的结点（包含起点和终点）里数额最大的赏金神符。 现在，阿畅想要知道：如果他随机选取起点和终点，最后能获得的金钱的期望值是多少？ 身为数学系的高材生，阿畅当然知道如何计算，但是他很忙，每天忙于睡觉，散步，打国战和制裁小人，所以他找到了你。请你帮阿畅算出所求的答案。
输入第一行是一个整数 n(2≤n≤105) ，代表河道地图所形成的树的结点个数。接下来的 n−1 行描述树的形状，每行两个数 u,v(1≤u,v≤n,u=v) ，代表结点 u 和v之间有一条边。第 n+1 行是 n 个正整数，第 i 个数 pi(1≤pi≤109) 表示结点 i 上的赏金神符所能提供的金钱。
输出一行一个数，代表阿畅所能获得金钱的期望值。为了精度考量，设答案为 ans ，请输出 ans×2n×(n−1) 的结果。聪明的你一定一眼就能看出，输出值就是阿畅所有起点和终点的不同选择的获得金钱总和，所以答案也一定是整数。
5
1 2
1 3
2 4
2 5
3 1 1 2 2
27
10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 1 1 1 1 1 1 1 1 1
45