【COGS2652】秘术「天文密葬法」

天文密葬法」"/>

【COGS2652】秘术「天文密葬法」

题目

思路

二分答案mid，那么显然我们要做的是check
于是乎，长链剖分维护即可

代码

#include<bits/stdc++.h>
#define eps 1e-5
using namespace std;
const int N=2e5+77;
int ls[N],Next[N<<1],ver[N<<1],cnt;
struct E
{int to,next;
}e[N<<1];
void add(int u,int v)
{e[++cnt].to=v,e[cnt].next=ls[u],ls[u]=cnt;
}
int n,m,a[N],b[N],len[N],son[N];
double val[N],tmp[N],*f[N],*id=tmp,ans=1e18,l,r,mid;
void dfs(int u,int fa)
{for(int i=ls[u]; i; i=e[i].next) if(e[i].to!=fa){dfs(e[i].to,u);if(len[e[i].to]>len[son[u]])son[u]=e[i].to;}len[u]=len[son[u]]+1;
}
void dp(int u,int fa)
{val[u]=a[u]-mid*b[u],f[u][0]=0;if(son[u])f[son[u]]=f[u]+1,dp(son[u],u),val[u]+=val[son[u]],f[u][0]-=val[son[u]];for(int i=ls[u]; i; i=e[i].next){int v=e[i].to;if(v==fa||v==son[u])continue;f[v]=id,id+=len[v],dp(v,u);for(int j=0;j<len[v]&&j<m;++j)if(m-j-1<len[u])ans=min(ans,f[v][j]+val[v]+f[u][m-j-1]+val[u]);for(int j=0;j<len[v]&&j<m;++j)f[u][j+1]=min(f[u][j+1],f[v][j]+val[v]-val[u]+a[u]-mid*b[u]);}if(m<len[u])ans=min(ans,f[u][m]+val[u]);
}
int main()
{scanf("%d%d",&n,&m); m--;for(int i=1; i<=n; i++) scanf("%d",&a[i]);for(int i=1; i<=n; i++) scanf("%d",&b[i]);for(int i=1; i<=n; i++) ans=min(ans,1.0*a[i]/b[i]);if(m==-2||!m){printf("%.2lf\n",ans); return 0;}for(int i=1,u,v; i<n; i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);dfs(1,0);l=0,r=N;while(r-l>eps){mid=(l+r)/2;memset(tmp,0x7f,sizeof(tmp)),ans=1e18;id=tmp,f[1]=id,id+=len[1],dp(1,0);if(ans>=0)l=mid;else r=mid;}if(l>=200000) printf("-1\n");else printf("%.2lf\n",l);
}