比赛 |
cdcqの省选膜你赛 |
评测结果 |
AAAAAWWWWWAWAAWAAAAA |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
65 |
用户昵称 |
11Dim |
运行时间 |
1.775 s |
代码语言 |
C++ |
内存使用 |
12.71 MiB |
提交时间 |
2017-04-11 11:39:22 |
显示代码纯文本
#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
const int MAXN = 200031;
const double EPS = 1e-4, INF = 1e6;
std::vector<int> g[MAXN];
double a[MAXN], b[MAXN], z[MAXN], d[MAXN], f[MAXN], h[MAXN];
bool vis[MAXN];
int sz[MAXN];
int gs(int u, int p) {
sz[u] = 1;
for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]] && g[u][i] != p) sz[u] += gs(g[u][i], u);
return sz[u];
}
int ctrd(int u, int p, int hs) {
for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]] && g[u][i] != p && sz[g[u][i]] > hs) return ctrd(g[u][i], u, hs);
return u;
}
int gd(int u, int p, int l) {
sz[u] = 1, d[u] = z[u] + d[p];
h[l] = std::min(h[l], d[u]);
for (int i = 0; i < g[u].size(); i++) if (!vis[g[u][i]] && g[u][i] != p) sz[u] += gd(g[u][i], u, l + 1);
return sz[u];
}
int n = 0, m = 0;
bool dc(int u) {
int ctr = ctrd(u, 0, gs(u, 0) / 2);
vis[ctr] = 1, d[ctr] = 0, sz[ctr] = sz[u];
std::fill(f, f + sz[ctr] + 1, INF);
std::fill(h, h + sz[ctr] + 1, INF);
f[1] = z[ctr];
double ans = INF;
for (int i = 0; i < g[ctr].size(); i++)
if (!vis[g[ctr][i]]) {
int v = g[ctr][i], sv = gd(v, ctr, 1);
for (int i = 1; i <= sv && i < m; i++) if (h[i] + f[m - i] < 0) return 1;
for (int i = 1; i <= sv; i++) f[i + 1] = std::min(f[i + 1], h[i] + z[ctr]);
std::fill(h, h + sv + 1, INF);
}
for (int i = 0; i < g[ctr].size(); i++) if (!vis[g[ctr][i]] && dc(g[ctr][i])) return 1;
return 0;
}
bool check(double x) {
std::fill(vis, vis + n + 1, 0);
for (int i = 1; i <= n; i++) z[i] = a[i] - x * b[i];
return dc(1);
}
int main() {
freopen("cdcq_b.in", "r", stdin);
freopen("cdcq_b.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lf", a + i);
for (int i = 1; i <= n; i++) scanf("%lf", b + i);
for (int i = 1, u = 0, v = 0; i < n; i++) scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
if (m == -1 || m == 1) {
for (int i = 1; i <= n; i++) z[i] = a[i] / b[i];
printf("%.2lf", *std::min_element(z + 1, z + n + 1));
} else {
double l = 0, r = INF;
for (double mid = 0; r - l > EPS; (check(mid = (l + r) / 2) ? r : l) = mid);
if (r == INF) puts("-1");
else printf("%.2lf\n", (l + r) / 2);
}
return 0;
}