比赛 cdcqの省选膜你赛 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 秘术「天文密葬法」 最终得分 100
用户昵称 cdcq 运行时间 9.925 s
代码语言 C++ 内存使用 7.06 MiB
提交时间 2017-04-11 12:38:18
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double oo=1e9;
const double eps=1e-6;
const int o_o=2000000001;
int rd(){int z=0,mk=1;  char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
	return z*mk;
}
struct ddd{int nxt,y;}e[210000];  int lk[110000],ltp=0;
inline void ist(int x,int y){  e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y;}
int n,m,a[110000],b[110000];
double c[110000],mn[110000],amn=oo;
bool vstd[110000];
double dstc[110000];  int dp[110000],f[110000],sz[110000];
int rt=0,cnt;
void gtrt(int x,int y){
	sz[x]=1;  f[x]=0;
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y] && e[i].y!=y){
		gtrt(e[i].y,x);
		sz[x]+=sz[e[i].y];
		f[x]=max(f[x],sz[e[i].y]);
	}
	f[x]=max(f[x],cnt-sz[x]);
	if(f[x]<f[rt])  rt=x;
}
void dfs(int x,int y,double z){
	dp[x]=dp[y]+1,dstc[x]=dstc[y]+c[x];
	if(dp[x]>m)  return ;
	int tmp=m-dp[x]+1;
	if(mn[tmp]<oo && mn[tmp]+dstc[x]-z<amn)
		amn=mn[tmp]+dstc[x]-z;
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y] && e[i].y!=y)
		dfs(e[i].y,x,z);
}
void updt(int x,int y){
	if(dp[x]>m)  return ;
	mn[dp[x]]=min(mn[dp[x]],dstc[x]);
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y] && e[i].y!=y)
		updt(e[i].y,x);
}
void clr(int x,int y){
	if(dp[x]>m)  return ;
	mn[dp[x]]=oo,dp[x]=0,dstc[x]=0;
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y] && e[i].y!=y)
		clr(e[i].y,x);
}
void ptt(int x){
	vstd[x]=true;  dstc[x]=c[x],dp[x]=1;  mn[1]=c[x];
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y]){
		dfs(e[i].y,x,dstc[x]);
		updt(e[i].y,x);
	}
	clr(x,0);
	for(int i=lk[x];i;i=e[i].nxt)if(!vstd[e[i].y]){
		cnt=sz[e[i].y];  rt=0;
		gtrt(e[i].y,0),ptt(rt);
	}
}
bool chck(double x){
	for(int i=1;i<=n;++i)  c[i]=(double)a[i]-x*b[i];
	amn=oo,cnt=n,f[0]=o_o,rt=0;
	for(int i=1;i<=m;++i)  mn[i]=oo;
	memset(vstd,0,sizeof(vstd));
	gtrt(1,0),ptt(rt);
	//cout<<clock()<<endl;
	return amn>0;
}
double bnrsch(){
	double l=0,r=oo,md;
	while(l+eps<r)  md=(l+r)/2,(chck(md) ? l : r)=md;
	return chck(r) ? r : l;
}
int main(){
	freopen("cdcq_b.in","r",stdin);
	freopen("cdcq_b.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;++i)  a[i]=rd();
	for(int i=1;i<=n;++i)  b[i]=rd();
	int l,r;
	for(int i=1;i<n;++i)  l=rd(),r=rd(),ist(l,r),ist(r,l);
	if(m==1 || m==-1){
		double ans=oo;
		for(int i=1;i<=n;++i)  ans=min(ans,a[i]*1.0/b[i]);
		printf("%.2lf\n",ans);
		return 0;
	}
	double ans=bnrsch();
	if(ans+eps>oo)  cout<<-1<<endl;
	else  printf("%.2lf\n",ans);
	//cout<<clock()<<endl;
	return 0;
}