记录编号	393813	评测结果	AAWAAATTTTAAAAAWAAAA
题目名称	秘术「天文密葬法」	最终得分	70
用户昵称	Ironk	是否通过	未通过
代码语言	C++	运行时间	14.590 s
提交时间	2017-04-12 09:32:36	内存使用	13.29 MiB

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef double DB;
typedef long long LL;
const DB EPS = 1e-3;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
inline int read() {
	register char ch = getchar();
	register int ans = 0, neg = 1;
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') neg = -1;
	for (; isdigit(ch); ch = getchar())
		ans = ans * 10 + ch - '0';
	return ans * neg;
}

int A[N], B[N];
vector <int> edge[N];

int root;
int cnt[N], minc = INF;
void dfsRoot(int a, int par) {
	cnt[a] = 1;
	int maxn = 0;
	for (int i = 0; i < edge[a].size(); ++i) {
		int now = edge[a][i];
		if (now == par) continue;
		dfsRoot(now, a), cnt[a] += cnt[now];
		maxn = max(maxn, cnt[now]);
	} maxn = max(maxn, n - cnt[a]);
	if (maxn < minc) minc = maxn, root = a;
}

void init() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) A[i] = read();
	for (int i = 1; i <= n; ++i) B[i] = read();
	for (int i = 1; i < n; ++i) {
		int a = read(), b = read();
		edge[a].push_back(b), edge[b].push_back(a);
	}
}

DB mid, dist[N];
int dep[N], size[N], fa[N];
int replc[N], plc[N], dfn;
void modify(int a, int par, DB add, int anc) {
	dist[plc[a]] += add, fa[plc[a]] = anc;
	for (int i = 0; i < edge[a].size(); ++i) {
		int now = edge[a][i];
		if (now == par) continue;
		modify(now, a, add, anc);
	}
}
struct Ary {
	int dep, fa; DB dist;
	Ary() {}
	Ary(int _dep, DB _dist, int _fa) : dep(_dep), dist(_dist), fa(_fa) {}
	inline bool operator < (const Ary &a) const {
		return dep != a.dep ? dep < a.dep : dist < a.dist;
	}
} ary[N];
inline void cls() {
	dfn = 0;
	for (int i = 1; i <= n; ++i) fa[i] = i;
}
bool dfs(int a, int par) {
	plc[a] = ++dfn, replc[dfn] = a;
	size[plc[a]] = 1, dep[plc[a]] = 0, fa[plc[a]] = a;
	dist[plc[a]] = mid * B[a] - A[a];
	if (edge[a].size() == 1) return false;
	for (int i = 0; i < edge[a].size(); ++i) {
		int now = edge[a][i];
		if (now == par) continue;
		if (dfs(now, a)) return true;
		size[plc[a]] += size[plc[now]];
	}
	ary[plc[a]] = Ary(dep[plc[a]], dist[plc[a]], a);
	for (int i = plc[a] + 1; i < plc[a] + size[plc[a]]; ++i)
		ary[i] = Ary(++dep[i], dist[i], fa[i]);
	sort(ary + plc[a], ary + plc[a] + size[plc[a]]);
	int pre = plc[a], nxt = plc[a] + size[plc[a]] - 1;
	while (pre < nxt) {
		while (ary[pre].dep + ary[nxt].dep > m - 1 && pre < nxt) nxt--;
		while (ary[pre].dep + ary[nxt].dep < m - 1 && pre < nxt) pre++;
		if (pre == nxt) break;
		if (ary[pre].dep + ary[nxt].dep == m - 1) {
			if (ary[pre].dep && ary[nxt].dep) {
				if (ary[pre].fa != ary[nxt].fa && ary[pre].dist + ary[nxt].dist + dist[plc[a]] + EPS > (DB)0)
					return true;
				else ++pre;
			} else {
				if (ary[pre].dist + ary[nxt].dist + EPS > (DB)0)
					return true;
				else ++pre;
			}
		}
	}
	for (int i = 0; i < edge[a].size(); ++i) {
		int now = edge[a][i];
		if (now == par) continue;
		modify(now, a, dist[plc[a]], a);
	}
	return false;
}

inline DB figure() {
	DB minn = INF;
	for (int i = 1; i <= n; ++i)
		minn = min(minn, (DB)A[i] / B[i]);
	if (m == -1 || m == 1) return minn;
	dfsRoot(1, 0);
	DB l = minn, r = 10, ans = -1;
	while (l + EPS <= r) {
		mid = (l + r) / 2;
		if (cls(), dfs(root, 0))
			r = mid, ans = mid;
		else l = mid;
	}
	return ans;
}

int main() {
	freopen("cdcq_b.in", "r", stdin);
	freopen("cdcq_b.out", "w", stdout);
	init();
	DB ans = figure();
	if (ans == -1.00) puts("-1");
	else printf("%.2lf\n", ans);
	return 0;
}