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