CF280C Game on Tree

发布于 2020-10-29  35 次阅读


link

Description

给出一棵树,每次随机等概率选择一未染黑的点,将它及其子树染黑。问期望多少次操作可以将树全部染黑。

Solution

考虑一个点和它的子树被删除的方式

如果这个点被删除了,只有可能是它的父亲一直到根的儿子节点的路径上的某一条边被删除了。

假设现在要删的点是u, 深度为dep_u, 选中这条路上的边有dep_u

因为我们只要删这条路上的一条边就可以把这个点删掉,所以期望是E(u) = \frac{1}{dep_u} * 1

所以答案是: \sum_{u} \frac{1}{dep_u}

注意dep_{root}要设成1

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;

int n, num;
int head[SIZE], dep[SIZE];
double ans, har[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void addEdge(int u, int v)
{
    edge[++ num].to = v, edge[num].nxt = head[u];
    head[u] = num;
}

inline void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    ans = ans + har[dep[u]];
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        if (v == fa) continue;
        dfs(v, u);
    }
}

signed main()
{
    n = read();
    for (int i = 1, u, v; i < n; ++ i) {
        u = read(), v = read();
        addEdge(u, v); addEdge(v, u);
    }
    dep[1] = 1;
    for (int i = 1; i <= n; ++ i) {
        har[i] = 1.00 / i;
    }
    dfs(1, 0);
    printf("%.6lf\n", ans);
    return 0;
}

朴实沉毅