Codeforces #362 Div1 B. Puzzles

ここらへんもまだまだ。
http://codeforces.com/contest/696/problem/B

問題

根付き木が与えられる。
この木をBFSで全頂点に訪問することを考えよう。
ただし、各頂点における各子頂点の訪問順はランダム(確率は等しい)とする。
各頂点が何番目に訪問されるか、その期待値を答えよう。

解法

頂点vの各子頂点w∈C(v)に対し、subtreeの頂点数S(w)の総和をsum(v)とする。
子頂点の対w1,w2に対しw1がw2より先に訪問する確率は1/2なので、その場合1/2の確率でw1以下の訪問順はS(w2)だけ遅れる。
これを全頂点対について考えると、w以下の頂点の訪問順は(sum(v)-S(w))/2だけ遅れる。

あとは上記計算をDFSで各頂点に対し順に行うだけ。

int N;
int P[101010];
int V[101010];
vector<int> E[101010];
double T[101010];

void dfs(int cur,double tim) {
	tim+=1;
	T[cur]= tim;
	FORR(r,E[cur]) {
		double el=(V[cur]-1-V[r])*0.5;
		dfs(r,tim+el);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<N;i++) cin>>P[i], P[i]--, E[P[i]].push_back(i);
	for(i=N-1;i>=0;i--) {
		V[i]++;
		if(i) V[P[i]]+=V[i];
	}
	
	dfs(0,0);
	FOR(i,N) _P("%lf%c", T[i],(i==N-1)?'\n':' ');
	
}

まとめ

この"stole my heart"の絵、あんまり問題の内容(≠ストーリー)と関係ないな…。