luogu

#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
const int Maxn=105;
const int Inf=1<<30;
const double eps=1e-4;
struct Edge{
int to,next;
}edge[Maxn<<1];
double d[Maxn],f[Maxn][Maxn];
int v[Maxn],c[Maxn],sz[Maxn],head[Maxn];
int n,m,Nedge;
inline int Min(int n,int m) {return n<m?n:m;}
inline int Max(int n,int m) {return n>m?n:m;}
inline int read() {
int w=0,x=0;char ch=0;
while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return w?-x:x;
}
inline void Add_Edge(int u,int v) {//邻接表建图
edge[Nedge]=(Edge){v,head[u]};
head[u]=Nedge++;
}
inline void dfs(int u,int fa) {//树背包
sz[u]=1;//将当前节点的子树节点设置为1
f[u][0]=0;//初始化
for (int i=head[u];i!=-1;i=edge[i].next) {//专属for
int v=edge[i].to;
if (v==fa) continue;//如果v=fa那么就跳出
dfs(v,u);//递归子树
sz[u]+=sz[v];//将子树的个数加到自己身上
for (int j=Min(m,sz[u]);j>=0;j--) {
for (int k=0;k<=Min(j,sz[v]);k++)
f[u][j]=Max(f[u][j],f[u][j-k]+f[v][k]);//背包
}
}
for (int i=min(m,sz[u]);i>0;i--) f[u][i]=f[u][i-1]+d[u];
}
inline bool judge(double x) {
for (int i=1;i<=n;i++)
for (int j=0;j<=m;j++) f[i][j]=-Inf;
for (int i=1;i<=n;i++) d[i]=(v[i]*1.0)-x*(1.0*c[i]);//01分数规划的基本操作
dfs(1,0);
for (int i=1;i<=n;i++)
if (f[i][m]>-eps) return 1;
return 0;
}
int main() {
ms(head,-1);
n=read(),m=read();
for (int i=1;i<=n;i++) v[i]=read();
for (int i=1;i<=n;i++) c[i]=read();
m=n-m;
for (int i=1;i<n;i++) {
int a=read(),b=read();
Add_Edge(a,b);
Add_Edge(b,a);
}
double l=0,r=1000000;
while (r-l>eps) {//在容许范围内那么就输出
double Mid=(l+r)/2.00;
if (judge(Mid)) l=Mid;
else r=Mid;
}
printf("%.1lf\n",l);
return 0;
}