You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

众所周知，动漫《海贼王》里有许多大海贼团，他们每个人都在海上有一定的领地。 今天世界政府想要评估一下当下海贼的势力值。为了简化计算，做如下设定，每个海贼团作为一个节点，单个海贼团有其威望值ai，当其作为整个海贼组织的领袖——海贼王时，对于海上的海贼势力值计算为 ，其中v表示当选海贼王的海贼团，dist(i,v)在海上i海贼团距离当前v海贼团的距离，其中这里的距离规定如果两个海贼团相连且有海路，则这两个海贼团之间距离为1。任意两个海贼团之间只有一条通路​。所以请你帮帮当下政府计算下所需要面对的海贼最大势力值为多少。

【输入格式】

第一行输入一个数n(1<=n<=2∗10​^5​),表示当下海贼团数量。

第二行输入n个数字a[i]表示每个海贼团的威望值(1<=a[i]<=5∗10​^5​)。

接下来的n−1行，每行输入u,v(1<=u,v<=n)u,v不同,表示u,v两个海贼团之间有一条海路。

【输出格式】

输出当下海贼最大势力值。

【输入样例】

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

【输出样例】

121

【样例解释】

上图为输入样例对应的图，当编号为3的海贼团当上海贼王时，其的势力值最大。2*9+1*4+0*1+3*7+3*10+4*1+4*6+4*5=18+4+0+21+30+4+24+20=121。

【数据规模】

对于30% 数据，1<=n<=1000,1<=a[i]<=5∗10^5

对于50% 数据，1<=n<=10000,1<=a[i]<=5∗10^5

对于100% 数据，1<=n<=2∗10​^5​,1<=a[i]<=5∗10^5