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