Background

I had so much certainty
Til that moment I lost control
And I've tried but it never was up to me
I've got no worse enemy
Than the fear of what's still unknown
And the time's come to realize there will be
Promises I can't keep

Problem Description

RFMC gives you a circuit and a power supply. He wants you to connect the power supply to some node of the circuit so that current can flow, and he promises to pay you an amount of money equal to the number shown on the circuit display.

This circuit has $n$ nodes. Each node has a weight $val_i$. The nodes are connected by $n - 1$ wires. You may connect the power supply to any starting node. Then the current starts flowing from that node. If the power supply is connected to a node $u$, then next the current will, with equal probability and without visiting any node more than once, flow to a leaf node. The sum of the weights of all nodes that the current passes through is the number shown on the display (a leaf node means a node of degree $1$ excluding $u$).

Now you have $n$ choices of where to connect the power supply. You want the expected score to be as large as possible after connecting it, so you need to compute, within the time limit, the maximum among these $n$ expected values.

Input Format

The first line contains an integer $n$, with the meaning as described above.

The next $n - 1$ lines each contain two integers $u, v$, indicating that there is a wire connecting nodes $u$ and $v$.

The next line contains $n$ integers. The $i$-th integer is $val_i$, the weight of node $i$.

Output Format

Output one floating-point number on one line, representing the maximum expected value.

This problem uses a special judge. Your answer will be accepted if its error from the correct answer does not exceed $10^{-2}$. The standard output keeps 4 decimal places.

5
1 2
1 5
2 3
2 4
2 3 1 -1 2

7.0000

Hint

Explanation for Sample 1:

When the power supply is connected to node 5, there are two possible paths: $5\rightarrow 1\rightarrow 2\rightarrow 3$ or $5\rightarrow 1\rightarrow 2\rightarrow 4$. The scores are 8 and 6 respectively, so the expected value is 7. It can be proven that no other starting node gives an expected value greater than 7.

This problem uses bundled tests. Each score tier corresponds to one subtask.

For $30\%$ of the testdata, it is guaranteed that $2 < n \le 10^3$.
For another $20\%$ of the testdata, it is guaranteed that the graph is a chain.
For all testdata, it is guaranteed that $2 < n \le 5\times 10^5,\ |val_i|\le 10^4$.

The special judge code for this problem is already provided in the attachment.

Note: The input size is large, so you may use a faster input method. (The reference solution can pass when using scanf.)

Postscript: According to the title, RFMC will not keep his promises (just kidding).

The title is actually the name of a song.

Translated by ChatGPT 5