题目描述

一棵 $n$ 个点的树，每个点两个点权 $a_i$ 和 $b_i$，找一条长度为 $m$ 的简单路径，使 $\frac{\sum a_i}{\sum b_i}$ 最小。无解输出 $-1$。

输入格式

第一行两个正整数 $n$ 和 $m$。
第二行 $n$ 个正整数 $a_i$。
第三行 $n$ 个正整数 $b_i$。
以下 $n-1$ 行，每行两个正整数 $u,v$，为一条边的两个端点。

输出格式

输出最小值，保留两位小数。

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

提示

subtask 1 $20$：$n\le 100$，$m\le n$，$1\le a_i,b_i\le 2000$。

subtask 2 $40$：$n\le 10^4$，$m\le n$，$1\le a_i,b_i\le 2000$。

subtask 3 $40$：$n\le 2\times 10^5$，$m\le n$，$1\le a_i,b_i\le 2000$。

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le m\le n$，$1\le a_i,b_i\le 2000$。