Description

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$.

Input Format

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 Format

Output the minimum value, rounded to two decimal places.

3 1
2 3 3
6 6 6
1 2
2 3

0.42

9 2
9 4 4 1 6 5 1 9 5
8 3 3 1 5 4 1 8 4
1 2
2 3
3 4
3 5
1 6
6 7
7 8
6 9

1.15

Hint

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