记录编号	393835	评测结果	WAWWWWWWWWWWWWWWAAAA
题目名称	秘术「天文密葬法」	最终得分	25
用户昵称	will	是否通过	未通过
代码语言	C++	运行时间	0.994 s
提交时间	2017-04-12 10:07:26	内存使用	13.26 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

const int MAXN=200005;
const double DINF=1e6, EPS=1e-6;

void rd(int &x){
	x=0; int ch=getchar();
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9') x=x*10+ch-'0', ch=getchar();
}

int N, M, G, ne, A[MAXN], B[MAXN];
double X[MAXN], tp[MAXN], re[MAXN];

struct Edge{
	Edge *nxt;
	int to, g;
}E[MAXN<<1], *hd[MAXN];

void adde(int u, int v){
	E[ne].to=v; E[ne].nxt=hd[u]; hd[u]=&E[ne++];
	E[ne].to=u; E[ne].nxt=hd[v]; hd[v]=&E[ne++];
}

int sz[MAXN], vis[MAXN];

int gs(int u, int p){
	sz[u]=1;
	for(Edge *e=hd[u]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]&&v!=p) sz[u]+=gs(v,u);
	}
	return sz[u];
}

int gg(int u, int p, int s){
	for(Edge *e=hd[u]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]&&v!=p&&sz[v]>s) return gg(v,u,s);
	}
	return u;
}

int m;
void gd(int u, int p, int d){
	m=max(m,d);
	for(Edge *e=hd[u]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]&&v!=p) return gd(v,u,d+1);
	}
}

int dc(int u){
	int g=gg(u,0,gs(u,0)>>1);
	vis[g]=1;
	for(Edge *e=hd[g]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]) e->g=dc(v);
	}
	return g;
}

void dfs(int u, int p, int d, double x){
	tp[d]=min(tp[d],x);
	for(Edge *e=hd[u]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]&&v!=p) dfs(v,u,d+1,x+X[v]);
	}
}

int work(int u){
	vis[u]=1; m=0; gd(u,0,1); 
	for(int i=1; i<m; ++i) re[i]=DINF;
	for(Edge *e=hd[u]; e; e=e->nxt){
		int v=e->to;
		if(!vis[v]){
			for(int i=1; i<m; ++i) tp[i]=DINF;
			dfs(v,u,1,X[v]);
			for(int i=0; i<m&&M-1-i>=0; ++i)
				if(tp[i]+re[M-1-i]+X[u]<EPS){return 1;}
			for(int i=1; i<m; ++i) re[i]=min(re[i],tp[i]);
		}
	}
	for(Edge *e=hd[u]; e; e=e->nxt){
		if(!vis[e->to]&&work(e->g)) return 1;
	}
	return 0;
}

int judge(double x){
	for(int i=1; i<=N; ++i) X[i]=A[i]-x*B[i];
	memset(vis,0,sizeof(vis));
	return work(G);
}

int main(){
	freopen("cdcq_b.in", "r", stdin);
	freopen("cdcq_b.out", "w", stdout);
	rd(N);scanf("%d",&M);
	for(int i=1; i<=N; ++i) rd(A[i]);
	for(int i=1; i<=N; ++i) rd(B[i]);
	if(M==-1){
		double ans=DINF;
		for(int i=1; i<=N; ++i) ans=min(ans,1.0*A[i]/B[i]);
		printf("%.2f", ans); return 0;
	}
	for(int i=1,u,v; i<N; ++i) rd(u),rd(v),adde(u,v);
	G=dc(1);
	double lb=0.0, ub=DINF;
	for(int i=0; i<40; ++i){
		double mid=lb+(ub-lb)*0.5;
		if(judge(mid)) ub=mid;
		else lb=mid;
	}
	if(ub>DINF/2) puts("-1");
	else printf("%.2f\n", ub);
	return 0;
}