Maximizing Expected Circuit Score

RFMC has given you a circuit and a power source. The circuit is a tree with n nodes, where each node i has a value \(val_i\). The nodes are connected by \(n-1\) wires so that the circuit is fully connected. You can attach the power source to any node as a starting point.

Once the power source is connected at a node \(u\), the current flows along a simple path (i.e. it will not visit any node more than once) until it reaches a leaf node. Note: A leaf node is defined as any node whose degree is 1 in the original circuit, except that the starting node \(u\) is never considered a leaf even if its degree is 1.

At each step, when the current is at a node \(v\) (with parent \(p\)), if there are one or more unvisited adjacent nodes, it chooses one uniformly at random to continue the flow. The process stops as soon as a leaf node is reached. The score displayed on the circuit is the sum of the values of all nodes that the current has flowed through (including both the starting node and the terminating leaf node).

Your task is to choose a starting node (among the \(n\) nodes) so that the expected score is maximized. More formally, if you attach the power source at node \(u\), let \[ F(u)=val_u+\begin{cases} \frac{1}{d(u)}\sum_{v\in adj(u)} f(v,u) &\text{if } d(u)\ge1,\\ 0 &\text{if } u \text{ has no adjacent node}, \end{cases} \] where for any node \(v\) with parent \(p\), \[ f(v,p)= \begin{cases} val_v &\text{if } v \text{ is a leaf (i.e. its only neighbor is } p\text{)},\\ val_v+\frac{1}{d(v)-1}\sum_{w\in adj(v)\setminus\{p\}} f(w,v) &\text{otherwise.} \end{cases} \] Compute \[ \max_{1\le u\le n} F(u). \]

Input guarantees: The circuit forms a tree (i.e. it is connected and has no cycles).

inputFormat

The first line contains an integer \(n\) representing the number of nodes in the circuit. The second line contains \(n\) space-separated integers \(val_1, val_2, \dots, val_n\), representing the value of each node. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) indicating that there is a wire connecting node \(u\) and node \(v\). Nodes are numbered from 1 to \(n\).

outputFormat

Output a single real number, the maximum expected score among all possible starting nodes. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3
1 2 3
1 2
2 3

6.000000