题目描述

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^{-4}$ 即可通过。

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

7.0000

解释 #1

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

数据范围

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