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