Codeforces #514 Div2 E. Split the Tree

方針はすぐ立ったのに、しょうもないバグを重ねたのが残念。
http://codeforces.com/contest/1059/problem/E

問題

根付き木を成すグラフが与えられる。
各頂点vには重みW[v]が設定されている。

このグラフの頂点群をいくつかの縦方向のパスに分離したい。
以下の条件を満たすパスに分離するとき、最小何個に分離できるか。

• 各パスは共通部分を持てない。
• 各パス上の頂点群はL個以下。
• 各パス上の頂点群の重みの合計はS以下。

解法

ダブリングと重みの総和の根頂点からの累積和を用いれば、各頂点に対し、その頂点を葉寄りの端点とするパスについて、根寄りの頂点が最長でどこまで伸ばせるかわかる。
後は葉から順に処理していく。
各頂点に子頂点がいくつかある場合、それらのうち根寄りの頂点が最も根に近くなる子頂点と連結していこう。
それ以外の子頂点は、親頂点（＝今処理している頂点）とつながらない。

int N,L;
ll S;
ll W[101010];
ll WS[101010];
int P[20][101010];
int C[101010];
vector<int> E[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>S;
	FOR(i,N) {
		cin>>W[i];
		if(W[i]>S) return _P("-1\n");
	}
	WS[0]=W[0];
	FOR(i,N-1) {
		cin>>P[0][i+1];
		P[0][i+1]--;
		E[P[0][i+1]].push_back(i+1);
		WS[i+1]=WS[P[0][i+1]]+W[i+1];
		
		FOR(j,19) P[j+1][i]=P[j][P[j][i]];
		
		x=y=i;
		for(j=19;j>=0;j--) {
			if((L-1)&(1<<j)) x=P[j][x];
			if(WS[i]-(WS[P[j][y]]-W[P[j][y]])<=S) y=P[j][y];
		}
		C[i]=max(x,y);
	}
	
	int ret=0;
	for(i=N-1;i>=0;i--) {
		int first=1;
		FORR(e,E[i]) if(C[e]>=0) {
			if(first==0) ret++;
			first=0;
			C[i]=max(C[i],C[e]);
		}
		
		if(C[i]==i) {
			ret++;
			C[i]=-1;
		}
	}
	cout<<ret<<endl;
}

まとめ

親頂点の番号が自身の番号より小さくなる表現方法、再帰を使わず全頂点辿れることが多いので好き。