Problem G
Great GDP
In your beloved homeland Treetopia, there is exactly one way of travelling between any pair of cites. In the loathful Cyclostan, on the other hand, there are exactly two ways of travelling between every pair of cities.
A delegation from Cyclostan is coming to visit Treetopia, and you realize that this is your big chance of persuading them to adopt the benefits of a tree-like society! Your friend Øyvind will decide on a travel plan for the Cyclostan delegation. In order to impress the delegation as much as possible, you persuade Øyvind to take them to parts of the country such that the GDP per capita is maximized across the visited cities. The trip can include visiting cities on several branches in the country, and it is not possible to travel through a city without visiting it.
The one and only airport in Treetopia is in the capital Treetopolis, and this is where the delegation from Cyclostan will arrive.
Input
The first line of input contains an integer $n$ ($1 \leq n \leq 100\, 000$), the number of cities in Treetopia. Then follows a line with $n$ non-negative integers $c_1, c_2, \dots c_ n$ ($0 \leq c_ i \leq 1\, 000\, 000$ for each $i \in \{ 1, 2, \ldots , n\} $), the GDP of each city. Then follows a line with $n$ positive integers $k_1, k_2, \dots , k_ n$ ($1 \leq k_ i \leq 1\, 000\, 000$ for each $i \in \{ 1, 2, \ldots , n\} $), the population of each city in Treetopia. Then follows $n-1$ lines, the $j^{\text {th}}$ of which with two distinct integers $u_ j$ and $v_ j$ ($1 \leq u_ j, v_ j \leq n$), indicating that there is a road between cities $u_ j$ and $v_ j$. Treetopolis is city number $1$.
Output
The highest possible GDP per capita of a connected region of Treetopia that contains Treetopolis. Any answer within an absolute or relative error of $10^{-6}$ will be accepted as a correct answer.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 10 40 1 2 10 1 2 1 3 |
4.33333333333 |
