Codeforces #513 F. Shrinking Tree

このDPは思いつかないわ。
http://codeforces.com/contest/1060/problem/F

問題

N頂点のラベル付きの木を成すグラフが与えられる。
この木について、以下の処理を等確率で頂点が１つになるまで繰り返す。

• 辺を１つ選び、両端の頂点を縮約する。その際、縮約後の頂点のラベルは両端のラベルのどちらかが等確率で選択される。

各ラベルが残る確率はいくつか。

解法

各ラベルに対し、その点rを根とする根付き木とみなして、根のラベルが最後まで残る確率を考えよう。

f(v,k) := ラベルvのSubTreeにおいて、k回辺の縮約が起きてもvが根として残る確率
とする。求めたいのは根頂点rに対しf(r,N-2)である。

f(v,k)を求めるにあたり、各子頂点cのsubtree内におけるf(c,l)を掛け合わせ、合計縮約数がk以下となるようにする。
さらにv-c間の縮約を行い合計k回の縮約となるケースを考えよう。
その際、v-c間の縮約が生じると1/2の確率でvのラベルは消える点に注意。

int N;
vector<int> E[55];
double dp[55][55];
int V[55];

double comb(int P_,int Q_) {
	static const int N_=102;
	static double C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
void dfs(int cur,int pre) {
	V[cur]=0;
	dp[cur][0]=1;
	int i,x,y;
	FORR(e,E[cur]) if(e!=pre) {
		double tmp[55]={},tmp2[55]={};
		dfs(e,cur);
		// cur-e側のsubtreeでx回耐える確率
		// ただしy回目にcur-e間の切断が起きる場合y<=xなら耐える確率半減
		FOR(x,V[e]+1) for(y=1;y<=V[e];y++) tmp[x]+=dp[e][min(x,y-1)]*(y<=x?0.5:1);
		// 接続済みsubtreeでx回、新規subtreeでy回耐える確率
		FOR(x,V[cur]+1) FOR(y,V[e]+1) {
			tmp2[x+y]+=dp[cur][x]*tmp[y]*comb(x+y,y)*comb(V[e]+V[cur]-x-y,V[e]-y);
		}
		FOR(i,N+1) dp[cur][i]=tmp2[i];
		V[cur]+=V[e];
	}
	V[cur]++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	double F=1;
	for(i=1;i<=N-1;i++) F*=i;
	
	FOR(i,N) {
		ZERO(dp);
		dfs(i,-1);
		_P("%.12lf\n",dp[i][N-1]/F);
	}
}

まとめ

状態遷移が複雑で、自分で解ける気がしない…。