树形 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。

#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;
}