6 - 海贼王（pirate）

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

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

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

对于 50% 数据 ，1≤n≤10000, 1≤ai≤5×10^5 对于 100% 数据，1≤n≤2×10^5, 1≤ai≤5×10^5
上图为输入样例对应的图，当编号为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。

2021年CCF线上测试