1297: 海贼王

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

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

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

接下来的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