比赛 |
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;
}
}
}