记录编号 | 393802 | 评测结果 | AAAAAAAAAAAAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | 秘术「天文密葬法」 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 0.920 s | ||
提交时间 | 2017-04-12 08:59:26 | 内存使用 | 13.45 MiB | ||
#include<cstdio> #include<cmath> const int len(200000); const double limt(2070707070.4646464); int n,m,a[len+10],b[len+10],x,y,all; struct Node{int nd,nx,root;}bot[len*2+10];int tot,first[len+10]; bool bf,flag[len+10]; double MID,l,r; void add(int a,int b){bot[++tot]=(Node){b,first[a],0};first[a]=tot;} template <class T>void umax(T &a,T b){if(a<b)a=b;} template <class T>void umin(T &a,T b){if(a>b)a=b;} template <class T> void read(T&x) { x=0;int f=0; char c=getchar(); while(c<'0'||c>'9'){f=(c=='-');c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x=f?-x:x; } namespace Dac { int size[len+10],big[len+10],root[len+10],color[len+10]; double dis[len+10],Last[len+10],NO,Root; void Get_size(int x,int f) { size[x]=1; big[x]=0; for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd] && bot[v].nd!=f) { Get_size(bot[v].nd,x); size[x]+=size[bot[v].nd]; umax(big[x],size[bot[v].nd]); } } void Get_root(int x,int f) { color[x]=color[f]; for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd] && bot[v].nd!=f) Get_root(bot[v].nd,x); umax(big[x],all-size[x]); if(big[x]*2<=all)root[color[x]]=x; } void Deal(int x) { flag[x]=1; Get_size(x,0); for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd]) { color[x]=bot[v].nd; all=size[bot[v].nd]; Get_root(bot[v].nd,x); bot[v].root=root[bot[v].nd]; } for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd]&&size[bot[v].nd]>=m)Deal(bot[v].root); } void Back() { for(int i=1;i<=m;i++)Last[i]=NO; for(int i=1;i<=n;i++)flag[i]=0; } void Run() { Get_size(1,0); NO=2070707070.4646464; Last[0]=0; for(int i=1;i<=m;i++)Last[i]=NO; for(int i=1;i<=n;i++) { umax(big[i],n-size[i]); if(big[i]*2<=n)root[0]=i; } Deal(root[0]); } void update(int x,int f,int d) { dis[x]+=a[x]-b[x]*MID; if(d>m)return; if(Last[m-d+1]!=NO&&Last[m-d+1]+dis[x]+Root<0)bf=true; if(d==m || bf)return ; for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd] && bot[v].nd!=f) dis[bot[v].nd]=dis[x],update(bot[v].nd,x,d+1); } void update_L(int x,int f,int d) { umin(Last[d],dis[x]); if(d==m || bf)return ; for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd] && bot[v].nd!=f)update_L(bot[v].nd,x,d+1); } void dfs(int x) { flag[x]=1; Last[1]=0; Root=a[x]-b[x]*MID; if(m==1&&Root<0){bf=true;return;} for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd]) { dis[bot[v].nd]=0; update(bot[v].nd,x,2); if(bf)break; update_L(bot[v].nd,x,2); } for(int i=1;i<=size[x]&&i<=m;i++)Last[i]=NO; if(bf)return; for(int v=first[x];v;v=bot[v].nx) if(!flag[bot[v].nd]&&size[bot[v].nd]>=m) { dfs(bot[v].root); if(bf)return ; } } } namespace ONE { void Run() { Dac::Run(); for(l=0,r=limt;r-l>1e-4;) { MID=(l+r)/2; bf=false; Dac::Back(); Dac::dfs(Dac::root[0]); (bf)?r=MID:l=MID; } MID=limt; bf=false; Dac::Back(); Dac::dfs(Dac::root[0]); if(!bf)printf("-1"); else printf("%.2f",l); } } namespace TWO { void Run() { double r=limt; for(int i=1;i<=n;i++)umin(r,(double)a[i]/b[i]); printf("%.2f",r); } } int main() { freopen("cdcq_b.in","r",stdin); freopen("cdcq_b.out","w",stdout); read(n);read(m); for(int i=1;i<=n;i++)read(a[i]); for(int i=1;i<=n;i++)read(b[i]); for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x); (m!=-1)?ONE::Run():TWO::Run(); return 0; }