题目背景

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

题目描述

RFMC 给了你一个电路，一个电源，他希望你能把电源接在电路的某一个节点上，让电流流通，并答应给你电路显示屏上的数那么多钱。

这个电路有 $n$ 个节点，每个节点有一个权值 $val_i$，以 $n-1$ 条导线互相连通。你可以把电源接在任意一个起点上。接着，电流从这个节点开始流。若当前电源接到了一个节点 $u$，则接下来电流会等概率且不重复经过一个点地流向一个叶子节点，电流流过的所有节点的权值即为电路显示屏上的数（叶子节点即为 除了 $u$ 的度数为 1 的节点）。

现在你有 $n$ 种接电源的选择，你希望接上电源以后期望得分越高越好，所以你现在就要在规定的时间内求出这 $n$ 种期望值中最大的的一个。

输入格式

第一行一个整数 $n$ 意义如题目所述。

接下来 $n-1$ 行每行两个整数 $u,\ v$，表示有一条联通编号为 $u,\ v$ 节点的导线。

接下来一行 $n$ 个整数，第 $i$ 个整数为 $val_i$，表示第 $i$ 个节点的权值。

输出格式

输出一行一个浮点数，表示最大期望值。

本题使用 special judge，你的答案和正确答案误差不超过 $10^{-2}$ 即可通过。标准答案保留 4 位小数。

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

7.0000

提示

样例一的解释：

电源接在 5 号节点时有两种情况：$5\rightarrow 1\rightarrow 2\rightarrow 3$ 或 $5\rightarrow 1\rightarrow 2\rightarrow 4$，两种情况得分分别为 8 和 6，期望值即为 7，可以证明没有其他节点接通电源的期望值比 7 大。

本题采用捆绑测试，每一档部分分对应一个 subtask。

对于 $30\%$ 的数据，保证 $2<n\le 10^3$。
对于另外 $20\%$ 的数据，保证是一条链。
对于所有的数据，保证 $2<n\le 5\times10^5,\ |val_i|\le10^4$。

本题的 special judge 代码已经在附件中给出。

附：本题数据量较大，可以采用更快的读入方法。（标程在用 scanf 的情况下可以通过）

后记：按照题目名称，RFMC 是不会遵守诺言的（大雾

题目名其实是一首歌名啦。