Codeforces #253 Div1 D. Adam and Tree

本番解ききれなかったが、Editorial見て解いてみた。
http://codeforces.com/contest/442/problem/D

問題

初期状態で1番の頂点1個がある。
ここに、この頂点を根とした根付き木となるよう、2～(N+1)番のN個の頂点を接続する。
それぞれ、接続先の親頂点p[i]が与えられる。

ここで、頂点同士を結ぶ辺に色をぬりたい。
色は以下の条件を満たさなければならない。

• 各頂点につながる辺において、3辺以上が同じ辺をもってはならない。
• 同じ色の辺につながる頂点は、同じ色の辺だけで連結しなければならない。

頂点を順々に追加したとき、木のコストは必要な色の最小数である。
2～(N+1)番の頂点を追加したときの木のコストを順次答えよ。

解法

各頂点x以下における必要色数をdp[x]とし、xにつながるsubtreeのうち色数の多い上位2位max1[x],max2[x]を管理していく。

新規頂点を追加したことで、max1[x],max2[x]が更新され、結果的にmax(max1[x],max2[x]+1)がdp[x]を超える場合、この頂点に新規色を割り当てなければならない。
そうでない場合、まだ2辺使ってない色があるので、その色を割り当てれば色を増やさずに済む。
…という処理を根に向けてdp[x]が更新される限り繰り返していく。

int N;
int P[1000002];
int dp[1000002];
int col[2][1000002];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>P[i];
		P[i]--;
		int cur = i;
		dp[cur]=1;
		while(cur>0) {
			int pa=P[cur];
			// set first and second maximum
			if(dp[cur]>col[0][pa]) col[1][pa]=col[0][pa],col[0][pa]=dp[cur];
			else col[1][pa]=max(col[1][pa], dp[cur]);
			// add new color but not increase cost
			if(max(col[0][pa],col[1][pa]+1) <= dp[pa]) break;
			dp[pa]=max(col[0][pa],col[1][pa]+1);
			cur = pa;
		}
		_P("%d ",col[0][0]);
	}
	_P("\n");
}

まとめ

同じ色の2辺が、親に1本使うのか、子だけで2本使うのかがややこしくて困っていたが、子の色数上位２つを管理すればよいのね。