比赛 |
cdcqの省选膜你赛 |
评测结果 |
WWAAAAAAAAAAAAAAWWWW |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
70 |
用户昵称 |
iortheir |
运行时间 |
11.473 s |
代码语言 |
C++ |
内存使用 |
11.76 MiB |
提交时间 |
2017-04-11 11:10:50 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 200000 + 10;
const double INF = 0x7fffffff;
const double eps = 1e-6;
int n;
int m;
int x;
int y;
int G[maxn];
int B[maxn];
struct T
{
int next;
int to;
}A[maxn];
int head[maxn];
int kount = 0;
double ha[maxn];
inline void adde(int u,int v)
{
A[++ kount].next = head[u];
A[kount].to = v;
head[u] = kount;
}
int mx[maxn];
double mi[maxn];
int vis[maxn];
int size[maxn];
double dis[maxn];
double maxx = INF;
int deep[maxn];
int root = 0;
int sum;
inline void isroot(int x,int fa)
{
mx[x] = 0;
size[x] = 1;
for(int i = head[x];i;i = A[i].next)
{
if(A[i].to != fa && !vis[A[i].to])
{
isroot(A[i].to,x);
size[x] += size[A[i].to];
mx[x] = max(mx[x],size[A[i].to]);
}
}
mx[x] = max(mx[x],sum - size[x]);
if(mx[x] < mx[root])
{
root = x;
}
}
inline void clear(int x,int fa)
{
if(deep[x] > m)
{
return ;
}
mi[deep[x]] = INF;
deep[x] = 0;
dis[x] = 0;
for(int i = head[x];i;i = A[i].next)
{
if(!vis[A[i].to] && A[i].to != fa)
{
clear(A[i].to,x);
}
}
}
inline void update(int x,int fa)
{
if(deep[x] > m)
{
return ;
}
mi[deep[x]] = min(mi[deep[x]],dis[x]);
for(int i = head[x];i;i = A[i].next)
{
if(!vis[A[i].to] && A[i].to != fa)
{
update(A[i].to,x);
}
}
}
inline void isdeep(int x,int fa,double w)
{
deep[x] = deep[fa] + 1;
dis[x] = dis[fa] + ha[x];
if(deep[x] > m)
{
return ;
}
int now = m - deep[x] + 1;
if(mi[now] < INF && mi[now] + dis[x] - w < maxx)
{
maxx = mi[now] + dis[x] - w;
}
for(int i = head[x];i;i = A[i].next)
{
if(!vis[A[i].to] && A[i].to != fa)
{
isdeep(A[i].to,x,w);
}
}
}
inline void dfs(int x)
{
vis[x] = 1;
dis[x] = ha[x];
deep[x] = 1;
mi[1] = ha[x];
for(int i = head[x];i;i = A[i].next)
{
if(!vis[A[i].to])
{
isdeep(A[i].to,x,dis[x]);
update(A[i].to,x);
}
}
clear(x,0);
for(int i = head[x];i;i = A[i].next)
{
if(!vis[A[i].to])
{
sum = size[A[i].to];
root = 0;
isroot(A[i].to,0);
dfs(root);
}
}
}
inline bool G_ha(double x)
{
for(int i = 1;i <= n; i ++)
{
ha[i] = (double)G[i] - x * B[i];
}
maxx = INF;
sum = n;
mx[0] = 2000000001;
root = 0;
for(int i = 1;i <= m; i ++)
{
mi[i] = INF;
}
memset(vis,0,sizeof(vis));
isroot(1,0);
dfs(root);
return maxx > 0;
}
inline double erfen()
{
double l = 0;
double r = INF;
double mid;
while(l + eps < r)
{
mid = (l + r) / 2;
if(G_ha(mid))
{
l = mid;
}
else
{
r = mid;
}
}
if(G_ha(r))
{
return r;
}
return l;
}
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",&G[i]);
}
for(int i = 1;i <= n; i ++)
{
scanf("%d",&B[i]);
}
for(int i = 1;i < n; i ++)
{
scanf("%d%d",&x,&y);
adde(x,y);
adde(y,x);
}
if(m == 1 || m == -1)
{
double ans = INF;
for(int i = 1;i <= n; i ++)
{
ans = min(ans,1.0 * G[i]/B[i]);
printf("%.2lf\n",ans);
return 0;
}
}
double ans = erfen();
if(ans + eps > INF)
{
cout<<-1<<endl;
}
else
{
printf("%.2lf\n",ans);
}
return 0;
}