You are given a tree with nodes rooted at node , and the -th node has a value . You need to assign a new value to each node, such that for each node and its parent . Output the minimum value of .

输入描述:

The first line contains an integer  indicating the number of nodes in the tree.
The second line contains  integers, and the -th integer  indicates the original value of the -th node.
Each of the next  lines contains two integers  and , indicating an edge between  and .

输出描述:

Output a real number indicating the minimum value of . Your answer will be considered correct if and only if the absolute or relative error of your answer to the correct answer is less than or equal to .

3
1 0 2
1 2
1 3

0.500000000

5
9 5 2 7 3
1 2
1 3
2 4
2 5

28.750000000

6
1 2 3 4 5 6
1 2
2 3
3 6
1 4
1 5

0.000000000