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