Codeforces ECR #028 : E. Chemistry in Berland

FよりEの方が難しかったみたいね。
http://codeforces.com/contest/846/problem/E

問題

N種類の硬貨がある。
各硬貨は両替できる硬貨が決められており、その関係は木を成す。
硬貨iを硬貨X[i](X[i]＜i)に両替するときのレートは1:1だが、硬貨X[i]を硬貨iに両替するときは硬貨iを1得るのに硬貨X[i]がK[i]かかる。

初期状態で各硬貨がA[i]枚ずつあるとき、両替によって各硬貨をB[i]以上にすることはできるか。

解法

硬貨の番号の大きな順に処理して行こう。
硬貨があまりそうならi→X[i]にあまり分を両替する。
逆に不足するならX[i]から高いレートで両替することにしよう。
最終的に根を成す硬貨で不足が生じたら条件を満たせない。
また、途中で不足分が十分に(例えば10^18以上)多くなった場合、他の余った硬貨で補填が効かないのでその場で処理を打ち切ってよい。

int N;
ll B[101010],A[101010];
int X[101010],K[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>B[i];
	FOR(i,N) cin>>A[i], B[i]-=A[i];
	for(i=1;i<N;i++) {
		cin>>X[i]>>K[i];
		X[i]--;
	}
	
	// go up
	for(i=N-1;i>0;i--) {
		if(B[i]>0) {
			B[X[i]]+=B[i];
		}
		if(B[i]<0) {
			if(B[i]<-1LL<<60) return _P("NO\n");
			if(B[i]*K[i]/K[i]!=B[i]) return _P("NO\n");
			if(B[X[i]]+B[i]*K[i]>B[X[i]]) return _P("NO\n");
			B[X[i]]+=B[i]*K[i];
		}
		B[i]=0;
	}
	if(B[0]<0) return _P("NO\n");
	
	_P("YES\n");
	
}

まとめ

双方向の両替レートの差がひどい。