[CF208C]Game on Tree

OI 题解 期望 数学

前置知识

• 期望的线性性质 ：$E(ax + by) = aE(x) + bE(y)$

解

考虑每个点，他因为选到自己而变黑的概率为$1/dep$，而某个点变黑的花费期望为$P($选中自己$) \cdot 1 + P($选到祖先$) \cdot 0 = 1/dep$.

所以总期望为每个点加起来。

代码

我竟然因为边表开小了WA了3次

#include<cstdio>
#include<iostream>
#include<iomanip>
using namespace std;
const int N = 100000 + 10;
int head[N], to[N * 2], next[N * 2], cnt;
long double ans;
int dep[N];
inline void adde(int x, int y) {
    ++cnt;
    to[cnt] = y;
    next[cnt] = head[x];
    head[x] = cnt;
}
void dfs(int x, int fa) {
    dep[x] = dep[fa] + 1;
    ans += 1.0 / (dep[x] * 1.0);
    for (register int i = head[x]; i; i = next[i]) {
        if (to[i] != fa) {
            dfs(to[i], x);
        }
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (register int i = 1, x, y; i < n; ++i) {
        scanf("%d %d", &x, &y);
        adde(x, y);
        adde(y, x);
    }
    dfs(1, 0);
//  printf("%.20llf\n", ans);
    cout << setprecision(20) << fixed << ans << endl;
    return 0;
}