比赛 |
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;
}