CF846E - Chemistry in Berland
阅读原文时间:2023年07月10日阅读:1

题意:有一颗树,每个点上有 \(b_i\) 东西,从叶子往上的汇率是 \(1:1\),从父亲往下的汇率是 \(k:1\),求能否使每个点的东西都不少于 \(a_i\)。

我们发现,从上往下肯定是不划算的,我们一定优先从下往上。而且一条边只经过一次,因为给 \(a\) 个拿回 \(b\) 个会导致总量减少,是不优的。可以通过退流得到最优答案。

而因为我们不需要最小化交易次数,所以我们允许交易过程中出现负数,因为先给出再补足和先补足再给出是等价的。假设当前方案是 \(b\rightarrow a\),\(c\rightarrow b\),而在中间过程中 \(b\) 出现了负数。但是 \(b\rightarrow a\) 是 \(a\) 和 \(b\) 所属的树的唯一一次交集,也就是两边是独立的,我们就完全可以先让 \(c\rightarrow b\) 先完成不会有影响。

那么,就有显然的贪心策略。从叶子开始,如果当前点不足,就向上面申请得到东西,所有多出来的不论青红皂白全部给到上面。不需要避免节点的负数,正常计算,最终看点 \(1\) 是否满足要求。

typedef long long ll;
ll n,p[100005],k[100005];
ll A[100005],B[100005];
__int128 a[100005],b[100005];
vt<int>vv[100005];
inline void dfs(int x,int p){
    for(auto j:vv[x])if(j!=p){
        dfs(j,x);
    }
    if(b[x]<a[x]&&p!=0){
        __int128 res=a[x]-b[x];
        b[p]-=res*k[x];b[x]+=res;
        if(b[p]<(-1e18)){
            cout<<"NO"<<endl;
            exit(0);
        }
    }else if(p!=0){
        b[p]+=(b[x]-a[x]);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    rp(i,n)cin>>B[i];
    rp(i,n)cin>>A[i];
    rp(i,n)a[i]=A[i],b[i]=B[i];
    rep(i,2,n){
        cin>>p[i]>>k[i];
        vv[p[i]].pb(i);
    }
    dfs(1,0);
    rp(i,n)if(b[i]<a[i]){
        cout<<"NO"<<endl;
        return 0;
    }
    cout<<"YES"<<endl;
    return 0;
}
//Crayan_r

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章