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

第一行输入一个数 $n\ (1 \leq n \leq 2 \times 10^5)$，表示当下海贼团数量。
第二行输入 $n$ 个数字 $a_i\ (1 \leq a_i \leq 5 \times 10^5)$ 表示每个海贼团的威望值。
接下来的 $n-1$ 行，每行输入 $u,\ v\ (1\leq u,\ v \leq n)\ u,\ v$ 不同,表示 $u,\ v$ 两个海贼团之间有一条海路。

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

对于 $50\%$ 数据 ，$1 \leq n \leq 10000,\ 1 \leq a_i \leq 5 \times 10^5$
对于 $100\%$ 数据，$1 \leq n \leq 2 \times 10^5,\ 1 \leq a_i \leq 5 \times 10^5$

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$。