← 返回题目
题库练习 规划
← 上一题 下一题 →

A1967 | 规划

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

输入格式

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

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

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

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

输出格式

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

输入输出样例

输入 #1
3 2
2 3 4
1 1 1
1 2
2 3
输出 #1
4.0
C++ 编辑器
输入
输出