比赛 cdcqの省选膜你赛 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 秘术「天文密葬法」 最终得分 100
用户昵称 chad 运行时间 6.382 s
代码语言 C++ 内存使用 13.29 MiB
提交时间 2017-04-11 12:00:00
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define FILE "cdcq_b"
#define db double
#define pii pair<int,int>
#define M 16
#define eps 1e-8
int read(){
    int x=0,f=1,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return f*x;
}
const int maxn=(int)2e5+20,inf=(int)1e9,mod=(int)1e9+7;
template<class T> inline bool cmax(T& a,T b){return a<b?a=b,true:false;}
template<class T> inline bool cmin(T& a,T b){return a>b?a=b,true:false;}
int n,m,a[maxn],b[maxn],limit;
db k=0;
struct node{
	int y,next;
}e[maxn<<1];
int len,linkk[maxn],siz[maxn],dep[maxn],flag=0;
void insert(int x,int y){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;}
int mx[maxn],vis[maxn];
ll suma[maxn],sumb[maxn];
db d[maxn];
void getroot(int x,int fa,int S,int& rt){
	siz[x]=1;
	for(int i=linkk[x];i;i=e[i].next){
		if(e[i].y==fa||vis[e[i].y])continue;
		getroot(e[i].y,x,S,rt);
		siz[x]+=siz[e[i].y];
		cmax(mx[x],siz[e[i].y]);
	}
	cmax(mx[x],S-siz[x]);
	if(mx[x]<mx[rt])rt=x;
}
void dfs3(int x,int fa){//更新
	if(dep[x]>m&&m>=0)return;
	if(m>=0)cmax(d[dep[x]],k*sumb[x]-suma[x]);
	else cmax(d[0],k*sumb[x]-suma[x]);
	for(int i=linkk[x];i;i=e[i].next){
		if(e[i].y==fa||vis[e[i].y])continue;
		dep[e[i].y]=dep[x]+1;
		suma[e[i].y]=suma[x]+a[e[i].y];
		sumb[e[i].y]=sumb[x]+b[e[i].y];
		dfs3(e[i].y,x);
	}
}
bool dcmp(db a){
	if(fabs(a)<=eps)return 0;
	else return 1;
}
void dfs2(int x,int fa){
	if(dep[x]>m&&m>=0)return;
	if(m>=0){
		if(suma[x]-k*sumb[x]<=d[m-dep[x]]&&m-dep[x]<=limit){
			flag=1;return;
		}
	}
	else if(suma[x]-k*sumb[x]<=d[0]){flag=1;return;}
	for(int i=linkk[x];i;i=e[i].next){
		if(e[i].y==fa||vis[e[i].y])continue;
		dep[e[i].y]=dep[x]+1;
		suma[e[i].y]=suma[x]+a[e[i].y];
		sumb[e[i].y]=sumb[x]+b[e[i].y];
		dfs2(e[i].y,x);
		if(flag)return;
	}
}
void qing(int x,int fa){
	if(dep[x]>m&&m>=0)return;
	d[dep[x]]=-inf;cmax(limit,dep[x]);
	for(int i=linkk[x];i;i=e[i].next){
		if(e[i].y==fa||vis[e[i].y])continue;
		dep[e[i].y]=dep[x]+1;
		qing(e[i].y,x);
	}
}
void solve(int x,int S){
	if(S<m)return;
	int rt=0;mx[0]=inf;
	getroot(x,0,S,rt);x=rt;limit=0;
	dep[x]=0;qing(x,0);
	vis[x]=1;dep[x]=0;suma[x]=a[x],sumb[x]=b[x];
	d[0]=k*sumb[x]-suma[x];if((m<0||m==0)&&a[x]*1.0/b[x]<=k){flag=1;return;}
	for(int i=linkk[x];i;i=e[i].next){
		if(vis[e[i].y])continue;
		dep[e[i].y]=dep[x]+1;
		suma[e[i].y]=a[e[i].y],sumb[e[i].y]=b[e[i].y];
		dfs2(e[i].y,x);
		if(flag)return;
		suma[e[i].y]=a[e[i].y]+suma[x],sumb[e[i].y]=b[e[i].y]+sumb[x];
		dfs3(e[i].y,x);
	}
	for(int i=linkk[x];i;i=e[i].next){
		if(vis[e[i].y])continue;
		solve(e[i].y,siz[e[i].y]);
		if(flag)return;
	}
}
int main(){
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
	n=read(),m=read()-1;int Max=0;
	up(i,1,n)a[i]=read(),cmax(Max,a[i]);
	up(i,1,n)b[i]=read();
	up(i,2,n){
		int x=read(),y=read();
		insert(x,y);insert(y,x);
	}
	db left=0,right=Max,ans=Max;
	while(right-left>=1e-4){
		memset(vis,0,sizeof(int)*n);
		k=(left+right)/2;flag=0;
		solve(1,n);
		if(flag)right=k,ans=k;
		else left=k;
	}
	if(!dcmp(ans-Max)){
		printf("-1\n");
		return 0;
	}
	printf("%.2lf\n",ans);
    return 0;
}