比赛 9.27练习赛 评测结果 WWAAAAEEEEEEEEEEEEEE
题目名称 秘术「天文密葬法」 最终得分 20
用户昵称 flyfree 运行时间 3.452 s
代码语言 C++ 内存使用 3.24 MiB
提交时间 2024-09-27 21:11:50
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1010
#define N 1000000000.0
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
ll n,m,idx,cnt;
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll a[MAXN],b[MAXN];
ll dep[MAXN],f[MAXN],son[MAXN],siz[MAXN],tp[MAXN],st[MAXN];
struct node{
	ll l,r,sum_a,sum_b;
}tr[MAXN*4];
struct re_node{
	ll sum_a,sum_b;
};
void build(ll x,ll y){
	nxt[++idx]=hd[x];
	hd[x]=idx;
	ed[idx]=y;
}
void push_up(ll now){
	tr[now].sum_a=tr[now*2].sum_a+tr[now*2+1].sum_a;
	tr[now].sum_b=tr[now*2].sum_b+tr[now*2+1].sum_b;
}
void tr_build(ll l,ll r,ll now){
	tr[now].l=l,tr[now].r=r;
	if(l==r)return;
	ll mid=(l+r)/2;
	tr_build(l,mid,now*2);
	tr_build(mid+1,r,now*2+1);
}
void tr_ad(ll p,ll w,ll now){
	if(tr[now].l==tr[now].r){
		tr[now].sum_a+=a[w],tr[now].sum_b+=b[w];
		return;
	}
	ll mid=(tr[now].l+tr[now].r)/2;
	if(p<=mid)tr_ad(p,w,now*2);
	else tr_ad(p,w,now*2+1);
	push_up(now);
}
void dfs1(ll now,ll fa){
	f[now]=fa,dep[now]=dep[fa]+1,siz[now]=1;
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==fa)continue;
		dfs1(y,now);
		siz[now]+=siz[y];
		if(siz[y]>siz[son[now]])son[now]=y;
	}
}
void dfs2(ll now,ll fnt){
	tp[now]=fnt;
	st[now]=++cnt;
	tr_ad(cnt,now,1);
	if(!son[now])return;
	dfs2(son[now],fnt);
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==son[now]||y==f[now])continue;
		dfs2(y,y);
	}
}
re_node tr_re(ll l,ll r,ll now){
	if(tr[now].l>=l&&tr[now].r<=r)return((re_node){tr[now].sum_a,tr[now].sum_b});
	re_node ans=(re_node){0,0};
	ll mid=(tr[now].l+tr[now].r)/2;
	if(l<=mid){
		re_node q=tr_re(l,r,now*2);
		ans.sum_a+=q.sum_a;
		ans.sum_b+=q.sum_b;
	}
	if(r>mid){
		re_node q=tr_re(l,r,now*2+1);
		ans.sum_a+=q.sum_a;
		ans.sum_b+=q.sum_b;
	}
	return ans;
}
double re_(ll x,ll y){
	ll len=0,sum_a=0,sum_b=0;
	while(tp[x]!=tp[y]){
		if(dep[tp[x]]<dep[tp[y]])swap(x,y);
		re_node q=tr_re(st[tp[x]],st[x],1);
		sum_a+=q.sum_a,sum_b+=q.sum_b;
		len+=-dep[tp[x]]+dep[x]+1;
		x=f[tp[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	re_node q=tr_re(st[x],st[y],1);
	len+=dep[y]-dep[x]+1;
	sum_a+=q.sum_a,sum_b+=q.sum_b;
	if(len!=m)return N;
	else return (double)((double)sum_a/(double)sum_b);
}
int main(){
	freopen("cdcq_b.in","r",stdin);
	freopen("cdcq_b.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read();
		build(x,y);
		build(y,x);
	}
	tr_build(1,n,1);
	dfs1(1,0);
	dfs2(1,1);
	double ans=N;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ans=min(ans,re_(i,j));
		}
	}
	if(ans==N)cout<<"-1";
	else printf("%.2lf",ans);
	return 0;
}