规划

二分答案,dp

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
const int maxn = 110;
typedef long double ld;
int n,m;
ld w1[maxn],w2[maxn];
inline void up(ld&x,ld y){if(x<y)x=y;}
int vis[maxn],size[maxn];
ld f[maxn][maxn];
struct T{
    int to,nxt;
}way[maxn<<1];
int h[maxn],num;
inline void adde(int x,int y){
    way[++num]={y,h[x]},h[x]=num;
    way[++num]={x,h[y]},h[y]=num;
}
inline void dfs(int x){
    *f[x]=0,f[x][1]=w1[x],vis[x]=size[x]=1;
    for(int i=h[x];i;i=way[i].nxt)
        if(!vis[way[i].to]){
            int t=way[i].to;
            dfs(way[i].to);
            size[x]+=size[t];
            for(int i=size[x];i;--i)
                for(int j=0;j<=size[t]&&j<i;++j)
                    up(f[x][i],f[x][i-j]+f[t][j]);
        }
    vis[x]=0;
}
inline int chk(ld p){
    static ld w[maxn],ret;
    for(int i=1;i<=n;++i)w[i]=w1[i],w1[i]-=w2[i]*p;
    ret=0,dfs(1);
    for(int i=1;i<=n;++i)w1[i]=w[i],up(ret,f[i][m]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=size[i];++j)
            f[i][j]=-1./0;
    return ret>0;
}
int main(){
    std::ios::sync_with_stdio(false),std::cin.tie(0);
    std::cin >> n >> m,m=n-m;
    for(int i=1;i<=n;++i)std::cin >> w1[i];
    for(int i=1;i<=n;++i)std::cin >> w2[i];
    for(int i=1,x,y;i<n;++i)std::cin >> x >> y,adde(x,y);
    ld l=0,r=1e6,ans=0;
    for(int t=0;t<60;++t){
        ld mid=(l+r)/2;
        if(chk(mid))l=mid,up(ans,l);
        else r=mid;
    }
    printf("%.1Lf
",ans);
}