P1642 Planning

There are $N$ factories connected by $N - 1$ roads, and any two factories are reachable. Each factory has a production value and a pollution value. Now we plan to demolish $M$ factories so that the remaining factories still form a single connected component and the value of total production divided by total pollution is maximized.

The first line contains two integers $N, M$ representing the number of factories and the number to demolish. The second line contains $N$ positive integers $w_i$, representing the production of each factory. The third line contains $N$ positive integers $c_i$, representing the pollution of each factory. Then follow $N - 1$ lines. Each line contains two positive integers $a, b$ ($1 \le a, b \le N$) indicating that $a$ and $b$ are connected.

Output the maximum value of total production divided by total pollution, rounded to one decimal place.

Constraints For all testdata, $1 < N < 100$, $1 \le M < N$, $1 \le w_i \le 10000$, and $1 \le c_i \le 10000$. Translated by ChatGPT 5