比赛 cdcqの省选膜你赛 评测结果 WWAAAWTTTTTTTTTTTWWT
题目名称 秘术「天文密葬法」 最终得分 15
用户昵称 confoo 运行时间 40.273 s
代码语言 C++ 内存使用 12.74 MiB
提交时间 2017-04-11 21:01:46
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <vector>
#define file(x) "cdcq_b."#x
#define fore for (int i = 0, v; i < (int)to[u].size(); i++) 
namespace I {
	const int L = 1 << 15 | 1;
	char *s, *t, buf[L];
	inline char gc() {
		if ( s== t) t = (s = buf) + fread(buf, 1, L, stdin);
		return *s++;
	}
	inline int gi() {
		int ch, r = 0;
		do ch = gc(); while (!isdigit(ch));
		for(;isdigit(ch);ch = gc()) r = r*10 + ch - '0';
		return r;
	}
}using I::gi;
const double EPS = 1e-4, INF = 1e18, eps = 1e-8;
const int V = 2e5 + 10;
inline int sgn(double x) {
	if (x < -eps) return -1;
	else if (x > eps) return 1;
	else return 0;
}
int n, m, a[V], b[V], q[V], h, t, sz[V], pre[V], vcn[V];
std::vector<int> to[V];
double ret, w[V], f[V], dis[V];
bool vis[V];
void solve(int u) {
	h = t = 0;
	pre[q[t++] = u] = 0;
	while (h < t) {
		int u = q[h++];
		sz[u] = 1;
		fore if (!vis[v=to[u][i]] && pre[v] != u) pre[q[t++] = v] = u;
	}
	for (int i = t; ~i; i--) sz[pre[q[i]]] += sz[q[i]];
	int size = sz[u];
	for (int flag = 1; flag; ) {
		flag = 0;
		fore if (!vis[v = to[u][i]] && v != pre[u] && sz[v] > size/2) {
			u = v;
			flag = 1;
			break;
		}
	}
	vis[u] = 1;
	static int modi[V], msz;
	fore if (!vis[v = to[u][i]]) {
		h = t = 0;
		pre[q[t++] = v] = u;
		int rt = u;
		int u = v;
		dis[u] = w[u];
		vcn[u] = 1;
		while (h < t) {
			int u = q[h++];
			if (vcn[u] < m) ret = std::min(ret, dis[u] + f[m - vcn[u] - 1] + w[rt]);
			fore if (!vis[v = to[u][i]] && v != pre[u]) {
				dis[v] = dis[u] + w[v];
				vcn[v] = vcn[u] + 1;
				pre[q[t++] = v] = u;
			}
		}
		for (int i = 0; i < t; i++) f[vcn[q[i]]] = std::min(f[vcn[q[i]]], dis[q[i]]), modi[msz++] = vcn[q[i]];
	}
	while (msz) f[modi[--msz]] = INF; 
	fore if (!vis[v = to[u][i]]) solve(v);
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	n = gi(), m = gi();
	double l = 0, r = 0;
	for (int i = 1; i <= n; i++) a[i] = gi(), f[i] = INF, r = std::max(r, 1.0*a[i]);
	for (int i = 1; i <= n; i++) b[i] = gi();
	for (int i = 1, u, v; i < n; i++) u = gi(), v = gi(), to[u].push_back(v),to[v].push_back(u);
	if (m == -1) {
		double ans = (double)a[1]/b[1];
		for (int i = 1; i <= n; i++) ans = std::min(ans, (double)a[i]/b[i]);
		printf("%.2lf\n", ans);
	}
	while (r - l > EPS) {
		double mid = (l + r)/2;

//		printf("%lf %lf %lf\n", l , mid, r);

		ret = INF;
		for (int i = 1; i <= n; i++) vis[i] = (pre[i] = sz[i] = dis[i] = 0), w[i] = a[i] - mid*b[i], f[i] = INF;
		solve(1);
		if (ret == INF) {
			puts("-1");
			return 0;
		}
		if (ret < -eps) r = mid;
		else l = mid;
	}
	printf("%.2lf", l);
}