Puzzles [Codeforces 362 : Div2 D, Div1 B]

問題

http://codeforces.com/contest/697/problem/D

要素 n の木がある。
この木を要素1からDFSで探索することを考える。

ある要素から子へ遷移するときに、時間を+1する。
ある要素からどの順番で子へ遷移するかはランダムに決定される。
時間は最初0とする。

この時、木の全ての要素における時間の期待値を求めよ。

1 <= n <= 10^5

帰納的考察(@torus711さんに教えてもらった)

1. まずは実験をする
2. 頑張って実験して、規則性見つけるんだ！
3. 見つけるんだ…
4. 見つけ…

終了

――壁――

5. 終わって@torus711さんのツイートを発見

やったこと　A: よくある，根までのクエリを答えられるようにして LCA から上を引くやつ．関係する頂点は O( Q log Q ) 個なので適当にやる　B: 頂点ごとに，子の部分木のサイズの列を考える．着目した子以外の頂点が先に探索される確率が全て 0.5 なことを使う

— とーらす (@torus711) 2016年7月14日

6. ある頂点の1つの子について考えると他の子が先に探索される確率は全て0.5となる
7. 理由とかも聞いたら教えてくれました
8. なるほどなぁ

9. という訳でやることは、子供の要素数を数える -> dfs()
10. もう一回DFSして期待値を計算する -> dfs2()

補足
11. 期待値はDPか考察ゲーだと思っているんですけど、他にある？
12. 数え上げとして考えると分かるとか？

実装

http://codeforces.com/contest/697/submission/19133143

int n;
vector<int> child[101010];
//-----------------------------------------------------------------
int cnt[101010];
void dfs(int i) {
	cnt[i] = 1;
	for (int j : child[i]) {
		dfs(j);
		cnt[i] += cnt[j];
	}
}
//-----------------------------------------------------------------
double ans[101010];
void dfs2(int i) {
	int sum = 0;
	for (int j : child[i]) sum += cnt[j];

	for (int j : child[i]) {
		ans[j] = ans[i] + 1 + (double)(sum - cnt[j]) / 2.0;
		dfs2(j);
	}
}
//-----------------------------------------------------------------
int main() {
	scanf("%d", &n);
	rep(i, 1, n) {
		int p; scanf("%d", &p); p--;
		child[p].push_back(i);
	}

	dfs(0);
	ans[0] = 1;
	dfs2(0);

	rep(i, 0, n) printf("%.10f ", ans[i]);
	printf("\n");
}