CF280C Game on Tree

传送门

蒟蒻初学概率与期望

这道题感觉非常玄幻 （虽然在大佬眼里只是一道水题）

思路

我们设 \(f_i\) 表示 \(i\) 被删除时选择了 \(i\) 的次数

显然 \(f_i=0/1\)

那么题目要求的其实就是 \(E(\sum f_i)\)

而有因为期望满足可加性

因此我们考虑求单个点的贡献 \(E(f_i)\)

显然，只有在恰好选到 \(i\) 点时，它才会有贡献，且为恰好选到 \(i\) 的概率

这就要求我们之前都不能选择 \(i\) 的祖先结点

那它的概率怎么算？一个很妙的想法，就是将树上的结点转化成一个序列，而选点就是每次选择一个最前面的数，将它以及它子树内的数都去掉

那么要恰好选择到 \(i\)，就要求 \(i\) 排在它所有祖先的前面

根据排列组合，这个概率显然是 \(\frac{1}{dep_i}\)（\(dep_i\) 表示 \(i\) 的深度，也就是 \(i\) 祖先树 +1）

最后将所有都加起来即可

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, cnt;
double ans;
struct Node
{
    int to, next;
}r[200005]; int he[100005];
inline void dfs(int now, int de, int fa)
{
    ans += 1.0 / de;
    for(int i = he[now]; i; i = r[i].next)
        if(r[i].to != fa) dfs(r[i].to, de + 1, now);
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads();
    for(int i = 1; i < n; i++)
    {
        int u = reads(), v = reads();
        r[++cnt] = (Node){v, he[u]}, he[u] = cnt;
        r[++cnt] = (Node){u, he[v]}, he[v] = cnt;
    }
    dfs(1, 1, 0);
    printf("%.7lf", ans);
    return 0;
}
cf题解概率dp

相关

标签