比赛 |
cdcqの省选膜你赛 |
评测结果 |
WWWWWATTTTWAWWAWAAAA |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
35 |
用户昵称 |
Menci |
运行时间 |
25.307 s |
代码语言 |
C++ |
内存使用 |
14.04 MiB |
提交时间 |
2017-04-11 11:52:12 |
显示代码纯文本
#include <cstdio>
#include <cassert>
#include <cfloat>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
const int MAXN = 200000;
struct Node {
std::vector<Node *> adj;
bool solved;
int size, dist;
int a, b;
double w, sum;
} N[MAXN + 1];
int n, m;
inline void addEdge(int s, int t) {
N[s].adj.push_back(&N[t]);
N[t].adj.push_back(&N[s]);
}
inline int calcSize(Node *v, Node *fa = NULL) {
v->size = 1;
for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
if (u != fa && !u->solved) {
v->size += calcSize(u, v);
}
}
return v->size;
}
inline Node *center(Node *v, Node *fa = NULL) {
for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
if (u != fa && !u->solved) {
if (u->size > v->size / 2) return center(u, v);
}
}
return v;
}
inline double calc(Node *root) {
static double minOfLen[MAXN + 1], minOfLenBefore[MAXN + 1];
if (minOfLen[0] == 0) { // Not inited
for (int i = 0; i <= n; i++) minOfLen[i] = minOfLenBefore[i] = DBL_MAX;
} else {
// for (int i = 0; i <= n; i++) assert(minOfLen[i] == DBL_MAX && minOfLenBefore[i] == DBL_MAX);
}
double minHalf = DBL_MAX, minHalfBefore = DBL_MAX, min = DBL_MAX;
static Node *all[MAXN + 1];
int cntAll = 0;
double res = DBL_MAX;
for (Node **p = &root->adj.front(), *u; p && p <= &root->adj.back() ? (u = *p) : NULL; p++) {
if (u->solved) continue;
std::queue<Node *> q;
q.push(u);
u->dist = 1;
u->sum = u->w;
minOfLenBefore[0] = root->w;
static Node *a[MAXN + 1];
int cnt = 0;
while (!q.empty()) {
Node *v = q.front();
q.pop();
a[++cnt] = v;
all[++cntAll] = v;
if (m == -1) {
minHalf = std::min(minHalf, v->sum);
min = std::min(min, v->sum);
if (minHalfBefore != DBL_MAX) min = std::min(min, minHalfBefore + v->sum);
} else {
if (v->dist < m) {
minOfLen[v->dist] = std::min(minOfLen[v->dist], v->sum);
if (minOfLenBefore[m - v->dist - 1] != DBL_MAX) {
min = std::min(min, v->sum + minOfLenBefore[m - v->dist - 1]);
}
}
}
for (Node **p = &v->adj.front(), *u; p && p <= &v->adj.back() ? (u = *p) : NULL; p++) {
if (!u->solved && !u->dist) {
u->dist = v->dist + 1;
u->sum = v->sum + u->w;
q.push(u);
}
}
}
if (m == -1) {
minHalfBefore = std::min(minHalfBefore, minHalf);
} else {
for (int i = 1; i <= cnt; i++) {
Node *v = a[i];
if (v->dist < m) {
minOfLenBefore[v->dist] = std::min(minOfLenBefore[v->dist], minOfLen[v->dist]);
minOfLen[v->dist] = DBL_MAX;
}
}
}
res = std::min(res, min);
}
if (m == -1) {
res = std::min(res, root->w);
res = std::min(res, minHalfBefore + root->w);
} else {
for (int i = 1; i <= cntAll; i++) {
Node *v = all[i];
if (v->dist < m) {
minOfLen[v->dist] = minOfLenBefore[v->dist] = DBL_MAX;
}
v->dist = 0;
}
minOfLen[0] = minOfLenBefore[0] = DBL_MAX;
}
for (int i = 1; i <= cntAll; i++) N[i].dist = 0;
return res;
}
inline double solve() {
std::stack<Node *> s;
s.push(&N[1]);
double res = DBL_MAX;
while (!s.empty()) {
Node *v = s.top();
s.pop();
Node *root = center(v);
root->solved = true;
res = std::min(res, calc(root));
for (Node **p = &root->adj.front(), *u; p && p <= &root->adj.back() ? (u = *p) : NULL; p++) {
if (!u->solved) s.push(u);
}
}
// printf("%lf %lf %lf %lf\n", N[1].w, N[2].w, N[3].w, res);
return res;
}
inline bool check(double k) {
for (int i = 1; i <= n; i++) {
N[i].solved = false;
N[i].w = N[i].a - k * N[i].b;
}
return solve() < 0;
}
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("%d", &N[i].a);
for (int i = 1; i <= n; i++) scanf("%d", &N[i].b);
for (int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(u, v);
}
calcSize(&N[1]);
double l = 0, r = 1e9;
while (r - l > 1e-3) {
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
double ans = (l + r) / 2;
if (ans > 1e8) puts("-1");
else printf("%.2lf\n", ans);
}