P6074 Minimum Path

You are given a tree with $n$ nodes. Each node has two weights $a_i$ and $b_i$. Find a simple path of length $m$ such that $\frac{\sum a_i}{\sum b_i}$ is minimized. If there is no solution, output $-1$.

The first line contains two positive integers $n$ and $m$. The second line contains $n$ positive integers $a_i$. The third line contains $n$ positive integers $b_i$. The following $n - 1$ lines each contain two positive integers $u, v$, which are the two endpoints of an edge.

Output the minimum value, **rounded to two decimal places**.

Subtask 1 ($20$ points): $n \le 100$, $m \le n$, $1 \le a_i, b_i \le 2000$. Subtask 2 ($40$ points): $n \le 10^4$, $m \le n$, $1 \le a_i, b_i \le 2000$. Subtask 3 ($40$ points): $n \le 2 \times 10^5$, $m \le n$, $1 \le a_i, b_i \le 2000$. For $100\%$ of the testdata: $1 \le n \le 2 \times 10^5$, $1 \le m \le n$, $1 \le a_i, b_i \le 2000$. Translated by ChatGPT 5