Codeforces #800 : Div1 B. Fake Plastic Trees

割と出来の良かった回。
https://codeforces.com/contest/1693/problem/B

問題

根付き木が与えられる。
各頂点には整数値が設定され、初期値は0である。

1点頂点を選び、根からその頂点に至るパス上の点に、根から昇順となるような整数値をそれぞれ加算することを考える。
各点、最終的な整数値の範囲が指定される。
最小何回値を加算すればよいか判定せよ。

解法

葉から順に決めていこう。
各点に対し、子頂点の設定値の総和が：

• その頂点の取りえる最小値以上である場合、min(子頂点の設定値の総和, その頂点最大値)をその点に設定する。
• その頂点の最小値より小さい場合、その点を終端とする処理を1回追加しなければならない。その場合、設定値はその点の最大値とする。

int T,N;
int P[202020];
int L[202020],R[202020];
ll V[202020];
vector<int> E[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		FOR(i,N) E[i].clear();
		for(i=1;i<N;i++) {
			scanf("%d",&P[i]);
			P[i]--;
			E[P[i]].push_back(i);
		}
		FOR(i,N) {
			scanf("%d%d",&L[i],&R[i]);
		}
		int ret=0;
		for(i=N-1;i>=0;i--) {
			V[i]=0;
			FORR(e,E[i]) V[i]+=V[e];
			if(V[i]>=L[i]) {
				V[i]=min((ll)R[i],V[i]);
			}
			else {
				ret++;
				V[i]=R[i];
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

これは割とすんなり。