记录编号	393846	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	秘术「天文密葬法」	最终得分	100
用户昵称	scpointer	是否通过	通过
代码语言	C++	运行时间	2.242 s
提交时间	2017-04-12 11:04:00	内存使用	7.94 MiB

    #include <cstdio>
    #include <vector>
    using namespace std;
     
    inline int RD()
    {
    	int res;char cr;
    	while( (cr=getchar())<'0' || cr>'9'); res=cr-'0';
    	while( (cr=getchar())>='0' && cr<='9') res=res*10+cr-'0';
    	return res;
    }
     
    #define N 200050
    #define eps 1e-5
    #define pb push_back
    #define VI vector<int>
    #define Min(a,b) ((a)<(b)?(a):(b))
    int ai[N],bi[N];
    int qlen;
    double ans,nowC;
     
    vector<int> eg[N];
     
    int vis[N],sz[N];
     
    int sz_dfs(int p,int fa)
    {
    	sz[p]=1;
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt] && pt!=fa)
    			sz[p]+=sz_dfs(pt,p);
    	}
    	return sz[p];
    }
     
    int halfsize;
    int findroot(int p,int fa)
    {
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt] && pt!=fa && sz[pt]>=halfsize)
    			return findroot(pt,p);
    	}
    	return p;
    }
     
    int tim[N],timetip;
    double mn[N];
    bool solve(int p,int fa,int flo,double tot)
    {
    	if(flo-qlen>0) return 0;
    	tot+=ai[p]-bi[p]*nowC;
    	if(tim[qlen-flo]==timetip && mn[qlen-flo]+tot<0)
    		return 1;
    	
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt] && pt!=fa)
    		{
    			if(solve(pt,p,flo+1,tot))
    				return 1;
    		}
    	}
    	return 0;
    }
    void add(int p,int fa,int flo,double tot)
    {
    	if(flo-qlen>0) return;
    	tot+=ai[p]-bi[p]*nowC;
    	if(tim[flo]<timetip)
    		tim[flo]=timetip,mn[flo]=tot;
    	else
    		mn[flo]=Min(mn[flo],tot);
    	
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt] && pt!=fa)
    			add(pt,p,flo+1,tot);
    	}
    }
     
    bool check(int p)
    {
    	tim[0]=++timetip;
    	mn[0]=ai[p]-bi[p]*nowC;
    	
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt])
    		{
    			if(solve(pt,p,1,0))
    				return 1;
    			add(pt,p,1,mn[0]);
    		}
    	}
    	return 0;
    }
     
    void divis(int p)
    {
    	sz_dfs(p,0);
    	halfsize=sz[p]>>1;
    	p=findroot(p,0);
    	double l=0,r=ans,mid;
    	while((r-l)>eps)
    	{
    		nowC=mid=(l+r)/2;
    		if(check(p)) r=mid;
    		else l=mid;
    	}
    	ans=Min(ans,r);
    	
    	vis[p]=1;
    	vector<int> &V=eg[p];
    	for(int i=0,lim=V.size();i<lim;i++)
    	{
    		int pt=V[i];
    		if(!vis[pt])
    			divis(pt);
    	}
    }
    int main()
    {
    	freopen("cdcq_b.in","r",stdin);
    	freopen("cdcq_b.out","w",stdout);
    	int n=RD();qlen=RD()-1;
    	for(int i=1;i<=n;i++)
    		ai[i]=RD();
    	for(int i=1;i<=n;i++)
    		bi[i]=RD();
    	if(qlen==-2 || qlen==0)
    	{
    		ans=ai[1]/((double)bi[1]);
    		for(int i=1;i<=n;i++)
    			ans=Min(ans,ai[i]/((double)bi[i]));
    		printf("%.2lf\n",ans);
    		return 0;
    	}
    	
    	ans=1e13;
    	for(int i=1;i<=n-1;i++)
    	{
    		int p1,p2;p1=RD();p2=RD();
    		eg[p1].pb(p2);eg[p2].pb(p1);
    	}
    	divis(1);
    	if(ans<5e12) printf("%.2lf\n",ans);
		else puts("-1");
    }