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

#include<cstdio>
#include<algorithm>
using namespace std;
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;
}
int q[N],size,s[N],big[N],h[N],fa[N];
bool vis[N],check;
db ans=2e5+1,dp[N],f[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;
	h[root]=0;
	q[size=1]=root;
	dp[root]=a[root]-ans*b[root];
	q[size=1]=root;
	f[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;
		dp[S]=dp[root]+a[S]-ans*b[S];
		q[++size]=S;
		for (int i=last+1;i<=size;i++){
			int v=q[i];
			if (h[v]<=m&&dp[v]+f[m-h[v]]<0) check=1;
			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;
				dp[u]=dp[v]+a[u]-ans*b[u];
				q[++size]=u;
			}
		}
		for (int i=last+1;i<=size;i++){
			int v=q[i];
			h[v]--;
			dp[v]-=dp[root];
			if (h[v]<=m) f[h[v]]=min(f[h[v]],dp[v]);
		}
	}
	for (int i=1;i<=size;i++){
		int v=q[i];
		fa[v]=0;
		f[h[v]]=1e20;
	}
	if (check) return;
	for (int i=head[root];i;i=next[i])
		if (!vis[w[i]]) solve(w[i]);
}
void solve(db l,db r){
	int L=int(l*100+0.5),R=int(r*100+0.5);
	if (L==R){ans=L*0.01;return;}
	ans=(l+r)*0.5;
	for (int i=1;i<=n;i++) vis[i]=0;
	check=0;
	solve(1);
	return check?solve(l,ans):solve(ans,r);
}
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++) f[i]=1e20;
	solve(0,2e5+1);
	end:if (ans<=2e5) printf("%.2lf\n",ans);else puts("-1");
	return 0;
}