CF 280C Game on Tree

题目描述

https://codeforces.com/contest/280/problem/C

Solution

我们利用随机变量指示器

我们令 $X_i$ 表示 $i$ 将自己染黑这个事件的随机变量指示器

则 $E(X)=E(\sum X_i)=\sum E(X_i)$

那么我们还是要算 $i$ 将自己染黑的概率，首先 $E(X_1)=1$，所以下文中讨论的 $i\neq 1$

考虑将点 $i$ 到 $1$ 的所有点拿出来，不妨设有 $n$ 个点

那么实际上对于这些点的选择的话，我们必须保证第一个就选 $i$，所以概率就是 $\frac{1}{n}$

下面都是废话

任何一个合法的操作序列等价于从这 $n$ 个点中选出 $k$ 个点，其中 $k$ 大于 $1$

因为 $1$ 一定要选，那么根据古典概型，似乎我们得到了这样一个答案 $\frac{2^{n-2}}{2^{n-1}}=\frac{1}{2}$

但其实这是一个经典的错误答案，因为每种操作序列的出现概率是不同的，但是我们转换之后却使得他们的概率变成一样的

所以我们要这样转换，任何一个合法的操作序列等价于从一个 1 到 $n$ 的排列中从左到右依次选择能选择的点

不妨令 $a_i$ 表示某一个操作序列的等价排列的个数，这样的话每种操作序列出现的概率用古典概型表示就是 $\frac{a_i}{n!}$

那么这样的话 $i$ 将自己染黑的概率就是 $\frac{(n-1)!}{n!}=\frac{1}{n}$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#define maxn 100010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dep[maxn]; double ans;
void dfs(int u, int fa) {
    ans += 1.0 / dep[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; dfs(v, u);
    }
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } dep[1] = 1; dfs(1, 0);
    cout << fixed << setprecision(7) << ans << "\n";
    return 0;
}