BLUESKY007喜欢种树。一天，她得到了一棵n个点的树，其中节点i重量为wi。在种树之前，BLUESKY007需要用起重机把树吊起。由于她只有一台起重机，所以她只能选择一个点作为受力点。根据BLUESKY007所在世界的物理知识，吊起一棵树需要做的功为w1*dis1+w2*dis2+...wn*disn，其中disi表示节点i与受力点之间的距离（边数）。
由于吊起这棵树的费用与所做的功正相关，所以BLUESKY007希望所做的功尽可能小。请你帮助她求出吊起这棵树所做的功的最小值。

第一行包含一个整数n，表示树的点数。
第二行包含n个整数w1,w2,…,wn，其中wi表示节点i的重量。
接下来的n-1行中，每行包含两个数u,v，表示u和v两点之间有连边。

一个整数，表示最小做功。

4
1 2 3 4
1 2
2 3
3 4

8

输入2
4
3 2 1 4
1 2
2 3
3 4

输出2
12

对于45%的数据，n≤1000。 
对于100%的数据，2≤n≤2*10^5，1≤wi≤10^8，1≤u,v≤n, u<>v。