Connected Subtree Maximum Average Fruit Value

Given a tree with N nodes. The tree is connected and acyclic, meaning there is exactly one path between any two nodes. Each node i has a fruit with value \( v_i \) and weight \( w_i \). You are required to choose a connected subtree (i.e. a set of nodes forming a connected component in the original tree) that contains at least K nodes so that the average fruit value is maximized.

The average value is defined as:

\[ \frac{\sum_{i \in S} v_i}{\sum_{i \in S} w_i} \]

where \( S \) is the set of selected nodes and \( |S| \ge K \).

Note: The selected nodes must form a connected part of the tree.

inputFormat

The first line contains two integers N and K, representing the number of nodes and the minimum required nodes in the selected subtree, respectively.

The following N lines each contain two integers \( v_i \) and \( w_i \), representing the value and weight of the fruit at node i (nodes are 1-indexed).

The next N - 1 lines each contain two integers u and v, indicating an edge between nodes u and v.

outputFormat

Output a single number, which is the maximum possible average fruit value (i.e. total value divided by total weight) obtainable from a connected subtree containing at least K nodes.

The answer is considered correct if its absolute or relative error does not exceed \( 10^{-6} \).

sample

3 2
10 2
20 3
30 5
1 2
2 3

6.000000