TopCoder SRM 677 Div1 Medium DiameterOfRandomTree

本番発想が一歩足りなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14102

問題

N頂点からなる木が与えられる。
各辺の長さは、それぞれ半々の確率で1か2である。

この木の直径の期待値を求めよ。

解法

グラフを根付き木と見なし、状態dp[頂点][頂点からSubTree内のもっとも最遠点までの距離][SubTree内の直径] := (そのような状態に至る確率)を更新していこう。
そうすると解はsum_{x,y}(dp[根][x][y] * y)となる。

状態はDFSの要領で更新していく。
頂点pのうち、いくつかの子頂点まで処理した結果をdp_old[p][xp_old][yp_old]とする。
次の子頂点cをDFSし、dp[c][xc][yc]を求めたとする。
するとxp,yp,xc,ycに対し、lをpとcの間の長さ(1または2)として以下のように状態を更新できる。

• 最遠点の距離xp_newはxp_oldとxc+lの大きい方
• 直径yp_newはyp_oldとycとxc+yc+lの最大値
• dp_new[p][xp_new][yp_new] += dp_old[p][xp_old][yp_old]*dp[c][xc][yc]*0.5 (0.5はlが1の場合と2の場合が半々のため

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

class DiameterOfRandomTree {
	public:
	
	void go(int cur,int pre) {
		int a,b,c,d,i;
		double from[110][110]={};
		double to[110][110];
		from[0][0]=1;
		
		FORR(tar,E[cur]) if(tar!=pre) {
			go(tar,cur);
			ZERO(to);
			
			FOR(a,103) FOR(b,103) if(from[a][b]>=1e-12) {
				FOR(c,103) FOR(d,103) if(dp[tar][c][d]>=1e-12) {
					for(i=1;i<=2;i++) {
						int longer=max(a,c+i);
						int dia=max(b,max(d,a+c+i));
						to[longer][dia] += from[a][b] * dp[tar][c][d] * 0.5;
					}
				}
			}
			swap(from,to);
		}
		memmove(dp[cur],from,sizeof(from));
		
	}
	
	double getExpectation(vector <int> a, vector <int> b) {
		int i,j;
		ZERO(dp);
		N=a.size()+1;
		
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			E[a[i]].push_back(b[i]);
			E[b[i]].push_back(a[i]);
		}
		go(0,-1);
		
		double ret=0;
		FOR(i,110) FOR(j,110) ret+=dp[0][i][j]*max(i,j);
		return ret;
		
	}
}

まとめ

これは解いておきたかった。