在你挚爱的祖国 Treetopia，任意两个城市之间都恰好有一条路径。而在令人厌恶的 Cyclostan，任意两个城市之间则恰好有两条路径。

Pixabay License, by Timofey Iasinskii/waiguobox

来自 Cyclostan 的代表团即将访问 Treetopia，你意识到这是一个说服他们采纳树状社会结构优势的大好机会！你的朋友 Øyvind 将为 Cyclostan 代表团制定旅行计划。为了尽可能给代表团留下深刻印象，你说服 Øyvind 带他们去往该国的部分地区，使得所访问城市的人均 GDP 最大化。旅行可以包括访问该国多个分支上的城市，且如果不经过一个城市，就无法通过它。

Treetopia 唯一的机场位于首都 Treetopolis，这也是 Cyclostan 代表团抵达的地方。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示 Treetopia 的城市数量。 接下来一行包含 $n$ 个非负整数 $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 1\,000\,000$，对于每个 $i \in \{1, 2, \dots, n\}$)，表示每个城市的 GDP。 接下来一行包含 $n$ 个正整数 $k_1, k_2, \dots, k_n$ ($1 \le k_i \le 1\,000\,000$，对于每个 $i \in \{1, 2, \dots, n\}$)，表示 Treetopia 每个城市的人口。 接下来 $n-1$ 行，第 $j$ 行包含两个不同的整数 $u_j$ 和 $v_j$ ($1 \le u_j, v_j \le n$)，表示城市 $u_j$ 和 $v_j$ 之间有一条道路。Treetopolis 是 1 号城市。

输出格式

输出包含 Treetopolis 的 Treetopia 连通区域所能达到的最高人均 GDP。任何绝对误差或相对误差在 $10^{-6}$ 以内的答案都将被视为正确答案。

样例

输入格式 1

3
3 10 40
1 2 10
1 2
1 3

输出格式 1

4.33333333333