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

#include<cstdio>
#include<cmath>

const int len(200000);
const double limt(2070707070.4646464);
int n,m,a[len+10],b[len+10],x,y,all;
struct Node{int nd,nx,root;}bot[len*2+10];int tot,first[len+10];
bool bf,flag[len+10];
double MID,l,r;

void add(int a,int b){bot[++tot]=(Node){b,first[a],0};first[a]=tot;}
template <class T>void umax(T &a,T b){if(a<b)a=b;}
template <class T>void umin(T &a,T b){if(a>b)a=b;}
template <class T> void read(T&x)
{
	x=0;int f=0; char c=getchar();
	while(c<'0'||c>'9'){f=(c=='-');c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	x=f?-x:x;
} 

namespace Dac
{
	int size[len+10],big[len+10],root[len+10],color[len+10];
	double dis[len+10],Last[len+10],NO,Root;
	void Get_size(int x,int f)
	{
		size[x]=1; big[x]=0;
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd] && bot[v].nd!=f)
		{
			Get_size(bot[v].nd,x);
			size[x]+=size[bot[v].nd];
			umax(big[x],size[bot[v].nd]);
		}
	}
	void Get_root(int x,int f)
	{
		color[x]=color[f];
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd] && bot[v].nd!=f) Get_root(bot[v].nd,x);
		umax(big[x],all-size[x]);
		if(big[x]*2<=all)root[color[x]]=x;
	}
	void Deal(int x)
	{
		flag[x]=1;
		Get_size(x,0);
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd])
		{
			color[x]=bot[v].nd; all=size[bot[v].nd];
			Get_root(bot[v].nd,x);
			bot[v].root=root[bot[v].nd];
		}
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd]&&size[bot[v].nd]>=m)Deal(bot[v].root);
	}
	void Back()
	{
		for(int i=1;i<=m;i++)Last[i]=NO;
		for(int i=1;i<=n;i++)flag[i]=0;
	}
	void Run()
	{
		Get_size(1,0); NO=2070707070.4646464;
		Last[0]=0;
		for(int i=1;i<=m;i++)Last[i]=NO;
		for(int i=1;i<=n;i++)
		{
			umax(big[i],n-size[i]);
			if(big[i]*2<=n)root[0]=i;
		}
		Deal(root[0]);
	}
	void update(int x,int f,int d)
	{
		dis[x]+=a[x]-b[x]*MID;
		if(d>m)return;
		if(Last[m-d+1]!=NO&&Last[m-d+1]+dis[x]+Root<0)bf=true;
		if(d==m || bf)return ;
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd] && bot[v].nd!=f)
		 dis[bot[v].nd]=dis[x],update(bot[v].nd,x,d+1);
	}
	void update_L(int x,int f,int d)
	{
		umin(Last[d],dis[x]);
		if(d==m || bf)return ;
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd] && bot[v].nd!=f)update_L(bot[v].nd,x,d+1);
	}
	void dfs(int x)
	{
		flag[x]=1; Last[1]=0; Root=a[x]-b[x]*MID;
		if(m==1&&Root<0){bf=true;return;}
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd])
		{
			dis[bot[v].nd]=0;
			update(bot[v].nd,x,2);
			if(bf)break;
			update_L(bot[v].nd,x,2);
		}
		for(int i=1;i<=size[x]&&i<=m;i++)Last[i]=NO;
		if(bf)return;
		for(int v=first[x];v;v=bot[v].nx)
		if(!flag[bot[v].nd]&&size[bot[v].nd]>=m)
		{
			dfs(bot[v].root);
			if(bf)return ;
		}
	}
}

namespace ONE
{
	void Run()	
	{
		Dac::Run();
		for(l=0,r=limt;r-l>1e-4;)
		{
			MID=(l+r)/2; bf=false; 
			Dac::Back();
			Dac::dfs(Dac::root[0]);
			(bf)?r=MID:l=MID;
		}
		MID=limt; bf=false; 
		Dac::Back(); Dac::dfs(Dac::root[0]);
		if(!bf)printf("-1");
		else printf("%.2f",l);
	}
}

namespace TWO
{
	void Run()
	{
		double r=limt;
		for(int i=1;i<=n;i++)umin(r,(double)a[i]/b[i]);
		printf("%.2f",r);
	}
}

int main()
{
	freopen("cdcq_b.in","r",stdin);
	freopen("cdcq_b.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i++)read(b[i]);
	for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x);
	(m!=-1)?ONE::Run():TWO::Run();
	return 0;
}