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