P3874 [TJOI2010] Cutting the Tree

Xiao A found a tree full of fruits in an orchard, and he came up with a mischievous idea: he plans to cut off part of the tree and take it home.

We can represent this tree as a tree-structured graph, meaning there is exactly one path between any two nodes. At each node $i$, there is a fruit with value $v_i$ and weight $w_i$. Xiao A wants to take away a connected part (or the whole) of the tree that contains at least $K$ nodes (that is, at least $K$ fruits), such that the average value of these fruits is as high as possible. The average value is defined as the total value of the fruits divided by their total weight. Note that the part Xiao A cuts must be a connected subgraph of the original tree.

The first line contains two numbers $N$ and $K$, representing the number of nodes in the tree and the minimum number of fruits Xiao A should take. The second line contains $N$ space-separated numbers, representing the value $v_i$ of the fruit at each node. The third line contains $N$ space-separated numbers, representing the weight $w_i$ of each fruit. The next $N - 1$ lines each contain two numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), indicating that there is an edge between nodes $a_i$ and $b_i$. The input is guaranteed to describe a valid tree.

Output one line containing a single number, the maximum possible average value, rounded to two decimal places.

- Constraints: - For $20\%$ of the testdata, $1 \le N \le 16$. - For $100\%$ of the testdata, $1 \le N \le 100$, $1 \le K \le N$, $1 \le v_i \le 10000$, $1 \le w_i \le 10000$. Translated by ChatGPT 5