前置
树形 dp，二分。
题意
本质上是一个树上背包，需要选不少于 \(k\) 个物品，每个物品有一个重量 \(w\) 和价值 \(v\)，求性价比最大值。
分析
既然是性价比，显然是分数规划。
先介绍一下分数规划是什么：
我们二分这个最大性价比。
假设当前枚举到 \(mid\)，则我们将每个点的价值修改为
\[v-mid \times w \]然后我们正常做树形 dp，然后统计一下是否有价值大于等于 \(0\) 的即可。
那么为什么这样呢？
假设性价比为 \(g\)，我们选的是
\[p_1,p_2,...p_s( k\le s \le n) \]则我们有
\[\frac {\sum_{i=1}^s{v_{p_i}}}{\sum_{i=1}^s{w_{p_i}}}=g \]进而可以推出
\[\sum_{i=1}^s{w_{p_i} \times g}=\sum_{i=1}^s{v_{p_i}} \]那么，当我们定义价值 \(val_i=v_i-w_i \times g\) 时，有
\[\sum_{i=1}^s{val_{p_i}}=0\ge0 \]成立，故以上算法正确。
实现
比较好说，先二分出来 \(g\)，然后跑树形背包即可，注意要一边计算大小 \(size_p\) 一边跑背包，不然复杂度 \(O(n^3)\)，加上二分可能 TLE。（虽然我没试过）
然后就是注意把精度卡到 \(0.0001\)，不然会 WA。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef double db;
int ver[N * 2], nxt[N * 2], hd[N], idx;
inline void add (int x, int y) {
ver[++idx] = y;
nxt[idx] = hd[x];
hd[x] = idx;
}
int n, w[N], v[N], k, s[N];
bool mk[N];
db dp[N][N], g[N];
void dfs (int u, int fa) {
dp[u][0] = 0; dp[u][1] = g[u]; s[u] = 1;
for (int i = hd[u]; i ;i = nxt[i]) {
int y = ver[i];
if (y == fa) continue;
dfs(y, u);
s[u] += s[y]; //注意size和dp要一起算
for (int j = min(n, s[u]);j >= 1;j--) { //处理背包
for (int z = 0;z <= min(j - 1, s[y]);z++) {
dp[u][j] = max(dp[u][j], dp[u][j - z] + dp[y][z]);
}
}
}
}
bool check (db x) {
for (int i = 1;i <= n;i++) g[i] = v[i] - x * w[i]; //处理val
for (int i = 1;i <= n;i++) for (int j = 0;j <= n;j++) dp[i][j] = -200000;
dfs(1, 0);
db res = -1;
for (int i = 1;i <= n;i++) for (int j = k;j <= n;j++) {
res = max(res, dp[i][j]);
}
if (res >= 0) return 1;
return 0;
}
int main () {
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> v[i];
for (int i = 1;i <= n;i++) cin >> w[i];
for (int i = 1;i < n;i++) {
int x, y;
cin >> x >> y;
add(x, y); add(y, x);
}
db l = 0, r = 200000; //二分
while (r - l > 0.0001) { //注意精度
db mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid - 0.0001;
}
printf("%.2lf", l);
return 0;
}