Codeforces #172 Div1. C. Game on Tree

さてC。あっさり解ける人には解けたようだ。
http://codeforces.com/contest/280/problem/C

問題

点1をrootとする木構造が与えられる。
ここでこの木構造に対し、いずれかの点を等確率で選び、その点および子の点をすべて削除するという作業を繰り返し行う。
全部の点が削除される（＝根である点1が削除される）までの削除回数の期待値を求めよ。

解法

実はこれはかなり簡単だったりする。
各点は選択されて消される場合と、親の点が選択されて一緒に消される場合がある。
ここで、各点が選択されて消される確率は、1/(rootからの深さ)になる。
これは(rootからの深さ)-1個の点より先に今見ている点が選択される確率と考えることができる。

よって、あとは全部の点に対し1/(rootからの深さ)を累積すればよい。

void dfs(int cur,int pre, int depth) {
	int i;
	RES += 1.0/depth;
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		dfs(tar,cur,depth+1);
	}
}

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t;
	
	N=GETi();
	FOR(i,N-1) {
		x=GETi()-1;
		y=GETi()-1;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	
	dfs(0,-1,1);
	_P("%.12lf\n",RES);
	
	return;
}

まとめ

気づいてしまえば非常に簡単な問題。
でも本番中にこううまく考え付かなかった…。