/(/text{Sol. Luogu P1642}/) 规划

题意：给一颗 /(n/) 个节点的树，每个节点都有权值 /(a_i,b_i/)，要求在树上选出 /(n-m/) 个连通的节点，最大化 /(x=/dfrac{/sum a_i}{/sum b_i}/)

/(/rm Sol./)
题目所给的式子中含有 /(/dfrac{/sum a_i}{/sum b_i}/) 这一项，我们无法确定到底是选 /(a_i/) 更大的还是 /(b_i/) 更大的，这时
我们就必须要将 /(a_i,b_i/) 这两项化为一个整体求解。

/(/begin{aligned}x=/dfrac{/sum a_i}{/sum b_i}///to /sum a_i=x/cdot /sum b_i ///to/sum a_i-x/cdot/sum b_i =0///to /sum(a_i-xb_i)=0/end{aligned}/)

我们发现这样就可以将 /(a_i,b_i/) 两个参数化为一个处理。这题的 /(x/) 显然是有单调性的，我们二分 /(x/) 的值，将其带入上式，在树上跑树形 /(dp/) （背包）求其最大值，若最大值 /(/ge 0/) 说明当前 /(x/) 满足题意， /(ans = L = mid/)，反之则 /(R = mid/)。

树形背包部分基本等于板子。

/(/rm Code:/)

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1e5 + 5;

#define db double 

db f[N][N], val[M], sum;
vector <int> Link[N];
db val1[M], val2[M];

int n, m;

void dp(int u, int Fa) {
    for(auto v : Link[u]) {
        if(v == Fa) continue;
        dp(v, u);
        for(int k = m; k; k--) 
            for(int j = k; j >= 0; j--) 
                f[u][k] = max(f[u][k], f[u][k - j] + f[v][j]); // 树形背包
    }
    for(int i = m; i >= 1; i--) f[u][i] = f[u][i - 1] + val[u]; // 为保证连通性强制取当前点
    sum = max(sum, f[u][m]); // 一边更新一遍取最大值
}

inline bool check(db x) {
    for(int i = 1; i <= n; i++) val[i] = val1[i] - x * val2[i]; // 统一计算权值
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            f[i][j] = -1e9; // 注意 f[i][0] = 0，不能全部 memset 为 -inf
    sum = -1.0;

    dp(1, 0);
    return sum >= 0;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    cin >> n >> m; m = n - m;
    for(int i = 1; i <= n; i++) cin >> val1[i];
    for(int i = 1; i <= n; i++) cin >> val2[i];
    for(int i = 1; i < n; i++) {
        static int x, y; cin >> x >> y;
        Link[x].push_back(y);
        Link[y].push_back(x);
    }

    db L = 0.0, R = 1e6, ans;
    while(L + 1e-5 < R) { // 二分答案
        db mid = (L + R) / 2;
        if(check(mid)) { ans = L = mid; }
        else R = mid;
    }
    printf("%.1lf", ans);
    return 0;
}