TopCoder SRM 643 Div2 Hard TheKingsTree

Codeforcesで多そうな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12857

問題

N頂点の根付き木が与えられる。
各頂点を赤か緑に塗り分けたい。
その時、各頂点に色を塗るコストは、(その頂点自身を含め)その頂点のサブツリーにおける同色の頂点の数である。

最小の塗り分けコストを求めよ。

解法

単純なDPで、子から順に状態として赤い頂点の数を持ち、対応する最小コストを求めていく。

各頂点では、各子頂点における赤頂点数とコストの和の最小値を計算する。
その上で、頂点を赤く塗った場合と緑に塗った場合の赤頂点数・コストを更新する。

int N;
vector<int> E[53];
int num[53];
int sc[53][53];

class TheKingsTree {
	public:
	
	void dfs(int cur) {
		int dp[55][55];
		int i,x,y;
		num[cur]=0;
		memset(dp,0x3f,sizeof(dp));
		dp[0][0]=0;
		FOR(i,E[cur].size()){
			int tar=E[cur][i];
			dfs(tar);
			FOR(x,num[cur]+1) FOR(y,num[tar]+1) dp[i+1][x+y]=min(dp[i+1][x+y],dp[i][x]+sc[tar][y]);
			num[cur]+=num[tar];
		}
		
		FOR(i,num[cur]+1) {
			sc[cur][i+1] = min(sc[cur][i+1], dp[E[cur].size()][i]+i+1);
			sc[cur][i] = min(sc[cur][i], dp[E[cur].size()][i]+(num[cur]-i)+1);
		}
		num[cur]++;
	}
	
	int getNumber(vector <int> parent) {
		int i;
		N=parent.size()+1;
		FOR(i,N) E[i].clear();
		memset(sc,0x3f,sizeof(sc));
		
		FOR(i,N-1) E[parent[i]].push_back(i+1);
		dfs(0);
		return *min_element(sc[0],sc[0]+num[0]+1);
	}
}

まとめ

木DPはどうもCodeforcesのイメージが強い。