比赛 cdcqの省选膜你赛 评测结果 WWAAAWAAAAAWAAWWAAAA
题目名称 秘术「天文密葬法」 最终得分 70
用户昵称 Cydiater 运行时间 5.741 s
代码语言 C++ 内存使用 7.37 MiB
提交时间 2017-04-11 12:24:52
显示代码纯文本
//B
//by Cydiater
//2017.4.11
#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <bitset>
#include <set>
#include <complex>
#include <vector>

using namespace std;

#define ll 		long long
#define db		double
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(int i=LINK[node];i;i=e[i].next)
#define FILE		"cdcq_b"
	
const int MAXN=2e5+5;
const db oo=5e10;
const db eps=1e-4;

int N,M,va[MAXN],vb[MAXN];
bool vis[MAXN];
db ans=oo,mn[MAXN],res=oo;

int dcmp(db x){
	if(fabs(x)<eps)return 0;
	return x<0?-1:1;
}

namespace Graph{
	struct edge{
		int y,next;
	}e[MAXN];
	int LINK[MAXN],len=0,siz[MAXN],mxsiz[MAXN],root;
	int sum;
	inline void insert(int x,int y){
		e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;
	}
	inline void Insert(int x,int y){
		insert(x,y);
		insert(y,x);
	}
	void mkrt(int node,int fa){
		siz[node]=1;mxsiz[node]=0;
		Auto(i,node)if(e[i].y!=fa&&!vis[e[i].y]){
			mkrt(e[i].y,node);
			siz[node]+=siz[e[i].y];
			cmax(mxsiz[node],siz[e[i].y]);
		}
		cmax(mxsiz[node],sum-siz[node]);
		if(mxsiz[node]<mxsiz[root])root=node;
	}
	void Go(int node,int fa,int deep,db dis,db k){
		if(deep>M)return;
		cmin(res,dis+mn[M-deep]);
		Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
			Go(e[i].y,node,deep+1,dis+va[e[i].y]-vb[e[i].y]*k,k);
	}
	void Mark(int node,int fa,int deep,db dis,db k){
		if(deep>M)return;
		cmin(mn[deep],dis);
		Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
			Mark(e[i].y,node,deep+1,dis+va[e[i].y]-vb[e[i].y]*k,k);		
	}
	void Clear(int node,int fa,int deep){
		if(deep>M)return;
		mn[deep]=oo;
		Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa)
			Clear(e[i].y,node,deep+1);
	}
	bool check(int node,db k){
		res=oo;
		Auto(i,node)if(!vis[e[i].y]){
			Go(e[i].y,node,2,va[node]-vb[node]*k+va[e[i].y]-vb[e[i].y]*k,k);
			Mark(e[i].y,node,1,va[e[i].y]-vb[e[i].y]*k,k);
		}
		Auto(i,node)if(!vis[e[i].y])
			Clear(e[i].y,node,1);
		return dcmp(res)<=0;
	}
	void Fix(int node,int fa){
		siz[node]=1;
		Auto(i,node)if(!vis[e[i].y]&&e[i].y!=fa){
			Fix(e[i].y,node);
			siz[node]+=siz[e[i].y];
		}
	}
	void Work(int node){
		vis[node]=1;
		db leftt=0,rightt=oo,mid;
		while(leftt+eps<rightt){
			mid=(leftt+rightt)/2;
			if(check(node,mid))	rightt=mid;
			else			leftt=mid;
		}
		if(check(node,leftt))		cmin(ans,leftt);
		else if(check(node,rightt))	cmin(ans,rightt);
		Fix(node,0);
		Auto(i,node)if(!vis[e[i].y]){
			sum=siz[e[i].y];
			root=0;
			mkrt(e[i].y,node);
			Work(root);
		}
	}
}using namespace Graph;

namespace solution{
	void Prepare(){
		scanf("%d%d",&N,&M);
		up(i,1,N)scanf("%d",&va[i]);
		up(i,1,N)scanf("%d",&vb[i]);
		up(i,2,N){
			int x,y;
			scanf("%d%d",&x,&y);
			Insert(x,y);
			if(M==-1){
				if(vb[i]!=0)cmin(ans,1.0*va[i]/vb[i]);
			}
		}
		mn[0]=0;
		up(i,1,N)mn[i]=oo;
	}
	void Solve(){
		if(M==-1){
			printf("%.2lf\n",ans);
			return;
		}
		mxsiz[0]=N+1;root=0;
		sum=N;
		mkrt(1,0);
		Work(root);
		if(ans==-oo){
			puts("-1");
			return;
		}
		printf("%.2lf\n",ans);
	}
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}