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

description

题面
给个树，第\(i\)个点有两个权值\(a_i\)和\(b_i\)，现在求一条长度为\(m\)的路径，使得\(\frac{\sum a_i}{\sum b_i}\)最小

data range

\[m\le n\le 2\times 10^5\]

solution

0/1分数规划？二分吧。
二分一个值\(S\),要使得\(\frac{\sum a_i}{\sum b_i}\le S\)
那么\[\sum(a_i-Sb_i)\le0\]
把每个点的点权做成这个，然后\(DP\ check\)最优答案是否\(\le 0\)就行

如何\(DP\)?
暴力的，\(f_{i,j}\)表示\(i\)子数内长度为\(j\)的链的最优解，转移是\(O(n^2)\)的

按照深度的树上\(DP\)可以使用长链剖分优化到\(O(n)\)

总复杂度就是\(O(nlog\sum w)\)

code

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FILE "cdcq_b"
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-4;
const int mod=998244353;
const int N=200010;
const dd pi=acos(-1);
const int inf=2147483647;
const ll INF=1e18+1;
const ll P=100000;
il ll read(){
    RG ll data=0,w=1;RG char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
    return data*w;
}

il void file(){
    srand(time(NULL)+rand());
    freopen(FILE".in","r",stdin);
    freopen(FILE".out","w",stdout);
}

int n,m;dd x[N],y[N];
int head[N],nxt[N<<1],to[N<<1],cnt;
int len[N],son[N];
void dfs1(int u,int fa){
    for(RG int i=head[u];i;i=nxt[i]){
        RG int v=to[i];if(v==fa)continue;
        dfs1(v,u);if(len[son[u]]<len[v])son[u]=v;
    }
    len[u]=len[son[u]]+1;
}

dd *pos,f[N],*A[N],tag[N],ans,K;
void dfs2(int u,int fa){
    pos++;A[u]=pos;dd *a=A[u];
    if(!son[u]){
        a[0]=x[u]*1.0-K*y[u];
        if(m==1)ans=min(ans,a[0]);
        return;
    }
    dfs2(son[u],u);

    tag[u]=tag[son[u]]+x[u]*1.0-K*y[u];
    a[0]=x[u]*1.0-K*y[u]-tag[u];
    dd *b;
    for(RG int i=head[u];i;i=nxt[i]){
        RG int v=to[i];if(v==fa||v==son[u])continue;
        dfs2(v,u);b=A[v];
        if(m==1)ans=min(ans,b[0]+tag[v]);
        else 
            for(RG int j=0;j<m-1&&j<len[v];j++)
                if(m-j-2<len[u])ans=min(ans,b[j]+tag[v]+a[m-j-2]+tag[u]);       
        for(RG int j=0;j<len[v];j++)
            a[j+1]=min(a[j+1],b[j]+tag[v]+x[u]*1.0-K*y[u]-tag[u]);
    }
    if(len[u]>=m)ans=min(ans,a[m-1]+tag[u]);
}

dd g[N];
void dfs3(int u,int fa){
    if(!son[u]){g[u]=x[u]*1.0-K*y[u];ans=min(ans,g[u]);return;}
    dfs3(son[u],u);if(g[son[u]]<0)g[u]+=g[son[u]];else g[u]=0;
    for(RG int i=head[u];i;i=nxt[i]){
        RG int v=to[i];if(v==fa||v==son[u])continue;
        dfs3(v,u);ans=min(ans,g[u]+x[u]*1.0-K*y[u]+g[v]);
        g[u]=min(g[u],g[v]);
    }
    g[u]+=x[u]*1.0-K*y[u];ans=min(ans,g[u]);
}

il bool check(){
    ans=INF;
    if(m!=-1){pos=f;memset(f,0,sizeof(f));dfs2(1,0);}
    else dfs3(1,0);
    return ans<eps;
}

int main()
{
    file();
    RG dd l=0,r=0,mid,as=-INF;
    scanf("%d%d",&n,&m);
    if(n==1||(m!=-1&&m>=n)){puts("-1");return 0;}
    for(RG int i=1;i<=n;i++){scanf("%lf",&x[i]);r+=x[i];}
    for(RG int i=1;i<=n;i++){
        scanf("%lf",&y[i]);
    }
    for(RG int i=1,u,v;i<n;i++){
        u=read();v=read();
        to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
        to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
    }
    dfs1(1,0);
    
    while(r-l>=eps){
        K=mid=(l+r)/2;
        if(!check())l=mid;
        else as=mid,r=mid;
    }
    
    if(as==-INF)puts("-1");
    else printf("%.2lf\n",as);
    return 0;
}