过年了，有N个小朋友在玩丢沙包的游戏。游戏是这样的，每个小朋友都有一个编号，编号是1...N。每个小朋友面前有ai个沙包，即编号为i的小朋友面前有ai个沙包。游戏规定：如果两个两个小朋友之间有一条直线，那么这两个小朋友之间就可以互相丢沙包。每个小朋友的力气都很大，一次可以丢任意数量的沙包。现在有N-1条直线，并且从任一小朋友均可通过一些直线将沙包传递到达任一其他小朋友。如果要想使每个小朋友的沙包数量一样多，请求出最少的丢沙包的次数。数据保证有解。

输入的第一行包含整数 N。

第二行包含空格分隔的整数 ai，其中 i=1…N。第i个整数表示编号i的小朋友有ai个沙包。

最后N-1行每行包含两个空格分隔的编号 ui,vi，表示有一条直线连接编号是 ui 和 vi两个小朋友。

一个整数，表示最少的丢沙包的次数。

2<=N<=2*10^5

1<=ai<=10^9

1<=ui,vi<=N

样例解释：

在这个例子中，共有十二个沙包和四个小朋友，这意味着每个小朋友最后必须有三个沙包。可以通过以下三次丢沙包完成。

1、3号小朋友1个沙包给2号小朋友。

2、4号小朋友丢2 个沙包给2号小朋友。

3、2号小朋友丢1个沙包给1号小朋友。