比赛 cdcqの省选膜你赛 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 秘术「天文密葬法」 最终得分 100
用户昵称 LoveYayoi 运行时间 9.316 s
代码语言 C++ 内存使用 65.17 MiB
提交时间 2017-04-11 12:23:35
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <string>
  6. #include <cstring>
  7. #include <cmath>
  8. #include <map>
  9. #include <stack>
  10. #include <set>
  11. #include <vector>
  12. #include <queue>
  13. #include <time.h>
  14. #define eps 10e-7
  15. #define INF 0x3f3f3f3f
  16. #define MOD 1000000007
  17. #define rep0(j,n) for(int j=0;j<n;++j)
  18. #define rep1(j,n) for(int j=1;j<=n;++j)
  19. #define pb push_back
  20. #define set0(n) memset(n,0,sizeof(n))
  21. #define ll long long
  22. #define iter(i,v) for(edge *i = head[v];i;i=i->nxt)
  23. #define max(a,b) (a>b?a:b)
  24. #define min(a,b) (a<b?a:b)
  25. //#define OJ
  26. using namespace std;
  27. char BUF[2000000*7*4],*buf;
  28. int read() {
  29. int x = 0;
  30. while (!isdigit(*buf)) { buf++; }
  31. while (isdigit(*buf)) { x = x * 10 + *buf++ - '0'; }
  32. return x;
  33. }
  34. int read_m() {
  35. int f = 1, x = 0;
  36. while (!isdigit(*buf)) { if (*buf++ == '-') f = -1;}
  37. while (isdigit(*buf)) { x = x * 10 + *buf++ - '0'; }
  38. return f*x;
  39. }
  40. char get_ch() {
  41. char c = getchar();
  42. while (!isalpha(c)) c = getchar();
  43. return c;
  44. }
  45. const int MAXINT = 1000;
  46. const int MAXNODE = 200010;
  47. const int MAXEDGE = 400010;
  48. struct edge {
  49. int u, v;
  50. edge *nxt;
  51. edge(int _u, int _v, edge *_nxt) {
  52. u = _u; v = _v; nxt = _nxt;
  53. }
  54. edge() {}
  55. }*head[MAXNODE], mp[MAXEDGE];
  56. int n, m, cnt, a[MAXNODE], b[MAXNODE], v[MAXNODE], sz[MAXNODE], mx_sz, ct, pmin, ok;
  57.  
  58. double c[MAXNODE], mint[MAXNODE] = {};
  59. void add_edge(int, int);
  60. void get_input();
  61. void tree_divide(int p);
  62. void work();
  63. void get_sz(int, int);
  64. void get_ct(int, int);
  65. void add_info(int, int, double, int);
  66. void get_ans(int, int, double, int);
  67. int check(double k) {
  68. rep1(i, n) c[i] = a[i] - b[i] * k;
  69. ok = 0;
  70. memset(v, 0, sizeof(v));
  71. tree_divide(1);
  72. if (ok) return 1; else return 0;
  73. }
  74. int main() {
  75. freopen("cdcq_b.in", "r", stdin);
  76. freopen("cdcq_b.out", "w", stdout);
  77. get_input();
  78. work();
  79. return 0;
  80. }
  81. void add_edge(int u, int v) {
  82. mp[cnt] = edge(u, v, head[u]);
  83. head[u] = &mp[cnt++];
  84. mp[cnt] = edge(v, u, head[v]);
  85. head[v] = &mp[cnt++];
  86. }
  87. void get_input() {
  88. BUF[fread(BUF,1,2000000*28,stdin)]=0;
  89. buf=BUF;
  90. n = read(); m = read_m();
  91. int u, v;
  92. rep1(i, n) a[i] = read();
  93. rep1(i, n) b[i] = read();
  94. rep0(i, n - 1) {
  95. u = read(); v = read();
  96. add_edge(u, v);
  97. }
  98. }
  99. void work() {
  100. double ans = 1e18;
  101. rep1(i, m) mint[i] = 1e18;
  102. if (m == -1) {
  103. rep1(i, n) ans = min(ans, a[i] / double(b[i]));
  104. printf("%.2lf\n", ans);
  105. }
  106. else {
  107. double l = 0, r = 200010, mid;
  108. int t = 50;
  109. while (t--) {
  110. mid = (l + r) / 2;
  111. if (check(mid)) r = mid;
  112. else l = mid;
  113. }
  114. if(l>200000) printf("-1\n");
  115. else printf("%.2lf\n", l);
  116. //printf("%d\n",clock());
  117. }
  118.  
  119. }
  120. void tree_divide(int p) {
  121. get_sz(p, 0);
  122. mx_sz = sz[p]; pmin = INF;
  123. rep1(i, mx_sz) mint[i] = 1e18;
  124. mint[0] = 0;ct=p;
  125. get_ct(p, 0);
  126. p = ct;
  127. if (m == 1 && c[ct] <= 0) ok = 1;
  128. iter(i, p) {
  129. if (v[i->v]) continue;
  130. get_ans(i->v, p, c[i->v], 1);
  131. add_info(i->v, p, c[i->v], 1);
  132. }
  133. v[p] = 1;
  134. iter(i, p) {
  135. if (v[i->v]) continue;
  136. tree_divide(i->v);
  137. }
  138. }
  139. void get_ans(int p, int fa, double tmp, int l) {
  140. if(l+1>m) return ;
  141. if (tmp + mint[m - l - 1] + c[ct] <= 0) ok = 1;
  142. iter(i, p) {
  143. if (v[i->v] || i->v == fa) continue;
  144. get_ans(i->v, p, tmp + c[i->v], l + 1);
  145. }
  146. }
  147. void add_info(int p, int fa, double tmp, int l) {
  148. if(l+1>m) return ;
  149. mint[l] = min(mint[l], tmp);
  150. iter(i, p) {
  151. if (v[i->v] || i->v == fa) continue;
  152. add_info(i->v, p, tmp + c[i->v], l + 1);
  153. }
  154. }
  155. void get_sz(int p, int fa) {
  156. sz[p] = 1;
  157. iter(i, p) {
  158. if (v[i->v] || i->v == fa) continue;
  159. get_sz(i->v, p);
  160. sz[p] += sz[i->v];
  161. }
  162. }
  163. void get_ct(int p, int fa) {
  164. iter(i, p) {
  165. if (v[i->v] || i->v == fa) continue;
  166. get_ct(i->v, p);
  167. if (max(sz[p], mx_sz - sz[p]) < pmin) {
  168. pmin = max(sz[p], mx_sz - sz[p]);
  169. ct = p;
  170. }
  171. }
  172. }