P1642 规划

题目描述

某地方有 $N$ 个工厂，有 $N-1$ 条路连接它们，且它们两两都可达。每个工厂都有一个产量值和一个污染值。现在工厂要进行规划，拆除其中的 $M$ 个工厂，使得剩下的工厂依然连成一片且总产量 / 总污染的值最大。

输入格式

第一行两个整数 $N,M$ 表示工厂个数和要拆除的个数。

第二行 $N$ 个正整数 $w_i$，表示每个工厂的产值 。

第三行 $N$ 个正整数 $c_i$，表示每个工厂的污染值。

接着 $N-1$ 行，每行两个正整数 $a,b\ (1 \le a,b \le N)$ 表示 $a,b$ 之间相连。

输出格式

输出 总产量/总污染 的最大值，保留4位小数。

输入输出样例 #1

输入 #1

3 2
2 3 4
1 1 1
1 2
2 3

输出 #1

4.0

说明/提示

数据范围及约定

对于全部数据，$1<N<5000$，$1 \le M<N$，$1\le w_i\le 10000$，$1\le c_i\le 10000$。