题意:有一颗树,每个点上有 \(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
标签:rp,CF846E,Berland,ll,cin,dfs,100005,Chemistry,rightarrow
From: https://www.cnblogs.com/jucason-xu/p/17148798.html