U162884 海贼王

众所周知，动漫《海贼王》里有许多大海贼团，他们每个人都在海上有一定的领地。今天世界政府想要评估一下当下海贼的势力值。

为了简化计算，做如下设定，每个海贼团作为一个节点，单个海贼团有其威望值 $a_i$ ，当其作为整个海贼组织的领袖——海贼王时，对于海上的海贼势力值计算为$\sum_{i=1}^{n}dist(i,v)*a_i$。 其中$v$表示当选海贼王的海贼团，$dist(i,v)$在海上$i$海贼团距离当前$v$海贼团的距离，这里的距离规定如果两个海贼团相连且有海路，则这两个海贼团之间距离为$1$。 任意两个海贼团之间只有一条通路。 所以请你帮帮当下政府计算下所需要面对的海贼最大势力值为多少。

第一行一个数$n$($1\leq n \leq 2e5$)，表示当下海贼团数量。 第二行$n$个数字$a[i]$表示每个海贼团的威力值($1 \leq a[i] \leq 5e5$) 接下来$n-1$行，每行两个正整数$u,v$($1 \leq u,v \leq n, u \neq v$)表示两个海贼团$u$和$v$之间有一条海路。

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