CF846E - Chemistry in Berland

题意：有一颗树，每个点上有 \(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

巴特西

CF846E - Chemistry in Berland

最新文章

热门文章