比赛 |
cdcqの省选膜你赛 |
评测结果 |
AAWWWATTTTTTTTTTWWWW |
题目名称 |
秘术「天文密葬法」 |
最终得分 |
15 |
用户昵称 |
再见 |
运行时间 |
30.407 s |
代码语言 |
C++ |
内存使用 |
28.33 MiB |
提交时间 |
2017-04-11 21:23:48 |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
int vis[200010],cnt,visone,n,m,tot,dep[200010],fa[200010],head[200010],next[400010],to[400010],Tfa[25][30010];
double a[200010],b[200010],suma[25][30010],sumb[25][30010],ans;
inline double min(double &aa,double &bb){return aa<bb?aa:bb;}
inline void swap(int &i,int &j){int t=i; i=j; j=t;}
inline void ae(int u,int v){
++tot; to[tot]=v;
next[tot]=head[u]; head[u]=tot;
}
void dfs(int u){
for(int p=head[u];p;p=next[p])
if(to[p]!=fa[u]){
fa[to[p]]=u;
dep[to[p]]=dep[u]+1;
dfs(to[p]);
}
}
inline void update(double K){
if(!visone) visone=true,ans=K;
else ans=min(ans,K);
}
inline void work(int u,int v){
double sa=0,sb=0; int LCA=0;
if(dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v],thedis=dep[u]+dep[v];
if(d+1>m) return;
for(int i=0;(1<<i)<=d;i++)
if(d&(1<<i)){
sa+=suma[i][u];
sb+=sumb[i][u];
u=Tfa[i][u];
}
for(int i=22;i>=0;i--)
if(Tfa[i][u]!=Tfa[i][v]){
sa+=suma[i][u]; sa+=suma[i][v];
sb+=sumb[i][u]; sb+=sumb[i][v];
u=Tfa[i][u]; v=Tfa[i][v];
}
LCA=u;
sa+=a[LCA]; sb+=b[LCA];
if(thedis-2*dep[LCA]+1==m)
update(sa/sb);
}
int Q[200010],dis[200010],qhead,tail;
double rsuma[200010],rsumb[200010];
int bfs(int s){
qhead=tail=0; Q[tail++]=s;
for(int i=1;i<=n;i++) dis[i]=0,rsuma[i]=rsumb[i]=0;
rsuma[s]=a[s]; rsumb[s]=b[s]; dis[s]=1;
while(qhead<tail){
int u=Q[qhead++];
for(int p=head[u];p;p=next[p])
if(!dis[to[p]]){
Q[tail++]=to[p];
dis[to[p]]=dis[u]+1;
rsuma[to[p]]=rsuma[u]+a[to[p]];
rsumb[to[p]]=rsumb[u]+b[to[p]];
}
}
int mx=1;
for(int i=1;i<=n;i++)
if(dis[i]>dis[mx])
mx=i;
return mx;
}
void extrawork(){
int u=bfs(1);
bfs(u);
for(int i=1;i<=n;i++)
if(dis[i]==m) update(rsuma[i]/rsumb[i]),vis[++cnt]=i;
else if(dis[i]==m+1) vis[++cnt]=i;
for(int j=1;j<=cnt;j++){
bfs(vis[j]);
for(int i=1;i<=n;i++)
if(dis[i]==m)
update(rsuma[i]/rsumb[i]);
}
if(!visone) printf("-1\n");
else printf("%.2lf\n",ans);
}
int main(){
freopen("cdcq_b.in","r",stdin);
freopen("cdcq_b.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
for(int i=1;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
ae(u,v); ae(v,u);
}
if(n<=30000){
dfs(1);
for(int i=1;i<=n;i++){
Tfa[0][i]=fa[i];
suma[0][i]=a[i];
sumb[0][i]=b[i];
}
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n;j++){
Tfa[i][j]=Tfa[ i-1 ][ Tfa[i-1][j] ];
suma[i][j]=suma[i-1][j]+suma[i-1][ Tfa[i-1][j] ];
sumb[i][j]=sumb[i-1][j]+sumb[i-1][ Tfa[i-1][j] ];
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
if(i==j&&m==1) update(a[i]/b[i]);
if(i!=j) work(i,j);
}
if(!visone) printf("-1\n");
else printf("%.2lf\n",ans);
}
else if(m==n-1)
extrawork();
else
printf("-1\n");
return 0;
}