E95 01分数规划+树上背包 P1642 规划

// 01分数规划+树上背包 复杂度：n*m*log(1e9)
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return f * x;
}
const int N = 5010, Inf = 1 << 30;
int head[N], idx;
struct E
{
	int to, ne;
} e[N << 1];
int n, m, a[N], b[N], sz[N];
double c[N], f[N][N];

void add(int u, int v)
{
	e[++idx] = {v, head[u]};
	head[u] = idx;
}
void dfs(int u, int fa)
{
	sz[u] = 1;
	f[u][0] = 0;
	for (int i = head[u]; i; i = e[i].ne)
	{
		int v = e[i].to;
		if (v == fa)
			continue;
		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] + c[u];
}
bool check(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++)
		c[i] = a[i] - x * b[i];
	dfs(1, 0);
	for (int i = 1; i <= n; i++)
		if (f[i][m] >= 0)
			return 1;
	return 0;
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		a[i] = read();
	for (int i = 1; i <= n; i++)
		b[i] = read();
	m = n - m;
	for (int i = 1; i < n; i++)
	{
		int a = read(), b = read();
		add(a, b);
		add(b, a);
	}
	double l = 0, r = 1000000;
	while (r - l > 1e-5)
	{
		double mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	printf("%.4lf\n", l);
	return 0;
}