比赛 cdcqの省选膜你赛 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 秘术「天文密葬法」 最终得分 100
用户昵称 LoveYayoi 运行时间 9.316 s
代码语言 C++ 内存使用 65.17 MiB
提交时间 2017-04-11 12:23:35
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <time.h>
#define eps 10e-7
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define rep0(j,n) for(int j=0;j<n;++j)
#define rep1(j,n) for(int j=1;j<=n;++j)
#define pb push_back
#define set0(n) memset(n,0,sizeof(n))
#define ll long long
#define iter(i,v) for(edge *i = head[v];i;i=i->nxt)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
//#define OJ
using namespace std;
char BUF[2000000*7*4],*buf;
int read() {
	int x = 0;
	while (!isdigit(*buf)) { buf++; }
	while (isdigit(*buf)) { x = x * 10 + *buf++ - '0'; }
	return x;
}
int read_m() {
	int f = 1, x = 0;
	while (!isdigit(*buf)) { if (*buf++ == '-') f = -1;}
	while (isdigit(*buf)) { x = x * 10 + *buf++ - '0'; }
	return f*x;
}
char get_ch() {
	char c = getchar();
	while (!isalpha(c)) c = getchar();
	return c;
}
const int MAXINT = 1000;
const int MAXNODE = 200010;
const int MAXEDGE = 400010;
struct edge {
	int u, v;
	edge *nxt;
	edge(int _u, int _v, edge *_nxt) {
		u = _u; v = _v; nxt = _nxt;
	}
	edge() {}
}*head[MAXNODE], mp[MAXEDGE];
int n, m, cnt, a[MAXNODE], b[MAXNODE], v[MAXNODE], sz[MAXNODE], mx_sz, ct, pmin, ok;

double c[MAXNODE], mint[MAXNODE] = {};
void add_edge(int, int);
void get_input();
void tree_divide(int p);
void work();
void get_sz(int, int);
void get_ct(int, int);
void add_info(int, int, double, int);
void get_ans(int, int, double, int);
int check(double k) {
	rep1(i, n) c[i] = a[i] - b[i] * k;
	ok = 0;
	memset(v, 0, sizeof(v));
	tree_divide(1);
	if (ok) return 1; else return 0;
}
int main() {
	freopen("cdcq_b.in", "r", stdin);
	freopen("cdcq_b.out", "w", stdout);
	get_input();
	work();
	return 0;
}
void add_edge(int u, int v) {
	mp[cnt] = edge(u, v, head[u]);
	head[u] = &mp[cnt++];
	mp[cnt] = edge(v, u, head[v]);
	head[v] = &mp[cnt++];
}
void get_input() {
	BUF[fread(BUF,1,2000000*28,stdin)]=0;
	buf=BUF;
	n = read(); m = read_m();
	int u, v;
	rep1(i, n) a[i] = read();
	rep1(i, n) b[i] = read();
	rep0(i, n - 1) {
		u = read(); v = read();
		add_edge(u, v);
	}
}
void work() {
	double ans = 1e18;
	rep1(i, m) mint[i] = 1e18;
	if (m == -1) {
		rep1(i, n) ans = min(ans, a[i] / double(b[i]));
		printf("%.2lf\n", ans);
	}
	else {
		double l = 0, r = 200010, mid;
		int t = 50;
		while (t--) {
			mid = (l + r) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		if(l>200000) printf("-1\n"); 
		else printf("%.2lf\n", l);
		//printf("%d\n",clock());
	}

}
void tree_divide(int p) {
	get_sz(p, 0);
	mx_sz = sz[p]; pmin = INF;
	rep1(i, mx_sz) mint[i] = 1e18;
	mint[0] = 0;ct=p;
	get_ct(p, 0);
	p = ct;
	if (m == 1 && c[ct] <= 0) ok = 1;
	iter(i, p) {
		if (v[i->v]) continue;
		get_ans(i->v, p, c[i->v], 1);
		add_info(i->v, p, c[i->v], 1);
	}
	v[p] = 1;
	iter(i, p) {
		if (v[i->v]) continue;
		tree_divide(i->v);
	}
}
void get_ans(int p, int fa, double tmp, int l) {
	if(l+1>m) return ;
	if (tmp + mint[m - l - 1] + c[ct] <= 0) ok = 1;
	iter(i, p) {
		if (v[i->v] || i->v == fa) continue;
		get_ans(i->v, p, tmp + c[i->v], l + 1);
	}
}
void add_info(int p, int fa, double tmp, int l) {
	if(l+1>m) return ;
	mint[l] = min(mint[l], tmp);
	iter(i, p) {
		if (v[i->v] || i->v == fa) continue;
		add_info(i->v, p, tmp + c[i->v], l + 1);
	}
}
void get_sz(int p, int fa) {
	sz[p] = 1;
	iter(i, p) {
		if (v[i->v] || i->v == fa) continue;
		get_sz(i->v, p);
		sz[p] += sz[i->v];
	}
}
void get_ct(int p, int fa) {
	iter(i, p) {
		if (v[i->v] || i->v == fa) continue;
		get_ct(i->v, p);
		if (max(sz[p], mx_sz - sz[p]) < pmin) {
			pmin = max(sz[p], mx_sz - sz[p]);
			ct = p;
		}
	}
}