Minimum Magic Path Value in a Tree

You are given a tree consisting of n nodes connected by undirected edges. Each node has an associated magic value.

We define the magic value of a path as the product of the magic values of all nodes on the path divided by the number of nodes in that path. For example, if a path contains two nodes with magic values \(3\) and \(5\), then the magic value of the path is \(\frac{3 \times 5}{2} = 7.5\).

Your task is to compute the minimum magic value among all possible paths in the tree.

Note: A path can consist of a single node.

inputFormat

The first line contains an integer n denoting the number of nodes. The second line contains n space-separated numbers representing the magic values of the nodes in order (1-indexed). Each of the following n - 1 lines contains two space-separated integers u and v which indicate an undirected edge between nodes u and v.

outputFormat

Output a single number representing the minimum magic value among all paths in the tree. It is guaranteed that the answer can be represented by a floating-point number.

sample

3
3 5 7
1 2
2 3

3