首页 > 其他分享 >CF846E - Chemistry in Berland

CF846E - Chemistry in Berland

时间:2023-02-23 17:25:07浏览次数:31  
标签:rp CF846E Berland ll cin dfs 100005 Chemistry rightarrow

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

相关文章

  • CF808G Anthem of Berland 解题报告
    Description给定$s$串和$t$串,其中$s$串包含小写字母和问号,$t$串只包含小写字母。假设共有$k$个问号。你需要给把每个问号变成一个小写字母,共有$26^k$种可能......
  • CF808G Anthem of Berland
    \(\mathcalLink\)大概知道两种DP方法。(\(n\logn\)做法太神了)方法一:设\(f_i\)表示\(t\)在\(s[1\cdotsi]\)最多出现次数。当最后一位不会被匹配时,答案为\(f_......
  • Chemistry class
    What'snumberofvalenceelectrons?Thenumberofvalenceelectronsisthenumberofelectronsintheoutermostshellofanatom.Theseelectronsaretheones......
  • Codeforces 1 C. Ancient Berland Circus
    题意:二维平面中,给定三个点,这三个点是正多边形的三个顶点,求正多边形最小的面积。思路:两对点分别求中垂线,相交点是多边形外接圆的圆心,圆心有了半径和角度也就有了,之后求一......
  • 6.CF431E Chemistry Experiment 权值线段树+二分
    6.CF431EChemistryExperiment权值线段树+二分给定数列,区间查询和,区间取模,单点修改。记录区间最大值,对于区间最大值小于模数的区间不予更新洛谷传送门:​​CF431EChemist......
  • Neural Message Passing for Quantum Chemistry
    目录概符号说明框架GilmerJ.,SchoenholzS.S.,RileyP.F.,VinyalsO.andDahlG.E.Neuralmessagepassingforquantumchemistry.InInternationalConferen......
  • CF1C Ancient Berland Circus
    给定\(3\)个点,求以这\(3\)个点为顶点的正多边形面积最小值。先以这张图为例,首先可以肯定圆的半径是确定的。根据秦九韶公式,有\(S_{\triangleABC}=\sqrt{p(p-a)(p......
  • CF808G Anthem of Berland
    给定\(s\)和\(t\),其中\(s\)中有\(k\)个?,求\(s\)补齐?后匹配\(t\)的最大次数。\(|s|\times|t|\leq10^7\)。先用一组数据\(HACK\)掉贪心做法:(贪心只......
  • CF431E Chemistry Experiment
    CF431EChemistryExperiment题目大意有\(n\)支试管,每支试管装有\(h_i\ml\)的水银。\(q\)次操作,操作有两种:1\(p\)\(x\):倒掉试管\(p\)的水银修改为\(x\ml\)。2\(......