TopCoder SRM 570 Div1 Medium CentaurCompany

問題

木が与えられる。
この木のそれぞれのノードを、1/2の確率で赤、1/2の確率で白に塗る。
塗り終えた後で、同じ色のノードを全て連結にするために、自由に辺を足す。


ただし、それぞれのノードに新たに追加できる辺は、
1本目は無料で、2本目以降は1ずつのコストがかかる。


このコストの期待値を求めよ。

制約条件

ノードの数≦36

方針

二つの色は対称なので、それぞれの色ごとに連結にするコストは同じ。
したがって、片方の色を連結にするコストを求めればいい。


その色の連結成分の個数をk個、その色のノードの個数をl個とすると、
k - 1本の辺が新たに必要で、これは2(k - 1)個のノードに接続する。
このうちl個は無料なので、2(k - 1) - lのコストがかかる。


連結成分の個数k, ノードの個数をkとしたときの確率は動的計画法により求まる。
dp[i][j][k][l]を、i番目の頂点以下の部分木について、
根の色がjであり、jの色の連結成分がk個あり、jの色のノードがl個あるような状態になる確率とする。


1の色のノードだけを数えるものとすると、
dp[i][0][0][0] = 0.5
dp[i][1][1][1] = 0.5としておいて、
全ての子についてテーブルの更新をすればよい。

ソースコード

int n;
vector<vi> e;
double dp[40][2][40][40];
void rec(int c, int p){
	
	dp[c][1][1][1] = 0.5;
	dp[c][0][0][0] = 0.5;
	
	rep(i, e[c].size()){
		int to = e[c][i];
		if(to == p) continue;
		
		rec(to, c);
		
		double next[2][40][40] = {};
		
		rep(cl, 2) rep(j, 40) rep(k, 40) if(dp[c][cl][j][k])
		rep(ccl, 2) rep(jj, 40) rep(kk, 40) if(dp[to][ccl][jj][kk]){
			
			int nj = j + jj - (cl && ccl);
			next[cl][nj][k + kk] += dp[c][cl][j][k] * dp[to][ccl][jj][kk];
		}
		rep(j, 2) rep(k, 40) rep(l, 40) dp[c][j][k][l] = next[j][k][l];
	}
}

class CentaurCompany {
	public:
	double getvalue(vector <int> a, vector <int> b) {
		n = a.size() + 1;
		e.clear(); e.resize(n);
		rep(i, n - 1){
			e[--a[i]].pb(--b[i]);
			e[b[i]].pb(a[i]);
		}
		memset(dp, 0, sizeof(dp));
		rec(0, 0);
		
		double e = 0;
		rep(i, 40) rep(j, 40){
			e += 2 * (dp[0][0][i][j] + dp[0][1][i][j]) * max(0, (i - 1) * 2 - j);
		}
		return e;
	}
}