A1967. 规划
编程题
省选/NOI-
知识点
题目描述
某地方有 $N$ 个工厂，有 $N-1$ 条路连接它们，且它们两两都可达。每个工厂都有一个产量值和一个污染值。现在工厂要进行规划，拆除其中的 $M$ 个工厂，使得剩下的工厂依然连成一片且总产量 / 总污染的值最大。
输入格式
第一行两个整数 $N,M$ 表示工厂个数和要拆除的个数。
第二行 $N$ 个正整数 $w_i$，表示每个工厂的产值 。
第三行 $N$ 个正整数 $c_i$，表示每个工厂的污染值。
接着 $N-1$ 行，每行两个正整数 $a,b\ (1 \le a,b \le N)$ 表示 $a,b$ 之间相连。
第二行 $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
说明/提示
### 数据范围及约定
对于全部数据，$1<N<100$，$1 \le M<N$，$1\le w_i\le 10000$，$1\le c_i\le 10000$。
对于全部数据，$1<N<100$，$1 \le M<N$，$1\le w_i\le 10000$，$1\le c_i\le 10000$。