欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[cogs2652]秘术「天文密葬法」

程序员文章站 2022-05-08 18:30:02
...

题意:就是每个点有权值\(a_i,b_i\),选出一条长为\(m\)的路径(这里的长指的是路径点数),并最小化\(\frac{\sum a_i}{\sum b_i}\)

先膜一下zsy大佬

首先这显然是个分数规划,我们二分一个答案\(mid\),判断\(\frac{\sum a_i}{\sum b_i}\leq mid\),即\(\sum a_i-mid\sum b_i\leq 0\)

后面这个显然可以dp,记\(f[u][j]\)表示从\(u\)往下的长度为\(j\)的链中最小的权值是多少,很明显可以\(O(n^2)\)转移

考虑如何优化,用长链剖分,每个节点继承它重儿子的信息,轻儿子的信息直接暴力合并

不知道什么是长链剖分的可以看看蒟蒻的笔记

不过因为每个节点继承它重儿子的信息后要全部加上自己的值,所以可以每个点开一个变量来表示加了多少

//minamoto
#include<bits/stdc++.h>
#define eps 1e-3
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){
    int res,f=1;char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=2e5+5;
int head[N],Next[N<<1],ver[N<<1],tot;
inline void add(int u,int v){ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
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=head[u];i;i=Next[i])if(ver[i]!=fa){
        dfs(ver[i],u);
        if(len[ver[i]]>len[son[u]])son[u]=ver[i];
    }
    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=head[u];i;i=Next[i]){
        int v=ver[i];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(){
//  freopen("testdata.in","r",stdin);    
    freopen("cdcq_b.in","r",stdin);
    freopen("cdcq_b.out","w",stdout);
    n=read(),m=read()-1;
    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)ans=min(ans,1.0*a[i]/b[i]);
    if(m==-2||!m)return printf("%.2lf\n",ans),0;
    for(int i=1,u,v;i<n;++i)u=read(),v=read(),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)puts("-1");else printf("%.2lf\n",l);
    return 0;
}