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

#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const int N=4e5+10;
typedef long long ll;
typedef double db;
int n,m,a[N],b[N],w[N],next[N],head[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
db ans=1e20;
struct pt{
	ll x,y;
	pt(ll X=0,ll Y=0){x=X;y=Y;}
	bool operator < (const pt a)const{return x==a.x?y>a.y:x<a.x;}
	void print()const{printf("%lld %lld\n",x,y);}
};
db k(pt x,pt y){
	if (x.x==y.x) return x.y<y.y?1e20:-1e20;
	return db(x.y-y.y)/(x.x-y.x);
}
typedef tree<pt,null_mapped_type,less<pt>,rb_tree_tag,tree_order_statistics_node_update> Tree;
struct convex_hall{
	Tree T;
	Tree::iterator x,l,r,ll,rr;
	void init(){
		T.clear();
		T.insert(pt(-1e10,1e17));
		T.insert(pt(-1e10-1,1e18));
		T.insert(pt(1e10,1e17));
		T.insert(pt(1e10+1,1e18));
	}
	void ins(pt v){
		T.insert(v);
		l=r=x=T.find(v);
		--l;++r;
		while (1){
			ll=l;--ll;
			if (k(*ll,*l)<k(*l,*x)) break;
			T.erase(l);
			l=ll;
		}
		while (1){
			rr=r;++rr;
			if (k(*x,*r)<k(*r,*rr)) break;
			T.erase(r);
			r=rr;
		}
		if (k(*l,*x)>k(*x,*r)) T.erase(x);
	}
	void query(pt x){
		int l=2,r=T.size()-3;
		if (l>r) return;
		while (l<r){
			int mid=(l+r)>>1;
			ll=T.find_by_order(mid);
			rr=T.find_by_order(mid+1);
			if (k(x,*ll)<k(x,*rr)) r=mid;else l=mid+1;
		}
		ll=T.find_by_order(l);
		ans=min(ans,k(x,*ll));
	}
}H[200010];
int q[N],size,s[N],big[N],h[N],fa[N];
bool vis[N];
ll sa[N],sb[N];
void solve(int x){
	q[size=1]=x;fa[x]=x;
	for (int i=1;i<=size;i++){
		int v=q[i];
		s[v]=1;big[v]=0;
		for (int i=head[v];i;i=next[i]){
			int u=w[i];
			if (vis[u]||fa[u]) continue;
			fa[u]=v;
			q[++size]=u;
		}
	}
	int root=x;
	for (int i=size;i;i--){
		int v=q[i],u=fa[v];
		if (big[v]<=size/2&&s[v]>=size/2) root=v;
		s[u]+=s[v];
		big[u]=max(big[u],s[v]);
		fa[v]=0;
	}
	vis[root]=1;
	q[size=1]=root;
	H[0].ins(pt(0,0));
	for (int i=head[root];i;i=next[i]){
		int S=w[i],last=size;
		if (vis[S]) continue;
		fa[S]=root;
		h[S]=2;
		sa[S]=a[root]+a[S];
		sb[S]=b[root]+b[S];
		q[++size]=S;
		for (int i=last+1;i<=size;i++){
			int v=q[i];
			if (h[v]<=m) H[m-h[v]].query(pt(-sb[v],-sa[v]));
			for (int i=head[v];i;i=next[i]){
				int u=w[i];
				if (fa[u]||vis[u]) continue;
				fa[u]=v;
				h[u]=h[v]+1;
				sa[u]=sa[v]+a[u];
				sb[u]=sb[v]+b[u];
				q[++size]=u;
			}
		}
		for (int i=last+1;i<=size;i++){
			int v=q[i];
			h[v]--;
			sa[v]-=a[root];
			sb[v]-=b[root];
			if (h[v]<=m) H[h[v]].ins(pt(sb[v],sa[v]));
		}
	}
	for (int i=1;i<=size;i++){
		int v=q[i];
		fa[v]=0;
		if (h[v]<=m) H[h[v]].init();
	}
	for (int i=head[root];i;i=next[i])
		if (!vis[w[i]]) solve(w[i]);
}
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",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	if (m==1||m==-1){
		for (int i=1;i<=n;i++) ans=min(ans,1.0*a[i]/b[i]);
		goto end;
	}
	for (int i=1;i<n;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		add(f,t);add(t,f);
	}
	for (int i=0;i<=m;i++) H[i].init();
	solve(1);
	end:if (ans<1e20) printf("%.2lf\n",ans);else puts("-1");
	return 0;
}