CF280C Game on Tree解题报告

解题报告

CF280C Game on Tree

更好的阅读体验

题意

• 给定一棵$n$个点的树，每次随机将一个未染黑的结点的子树全部染黑，求将整棵树染黑的期望次数。
• 数据范围：$1\leqslant n\leqslant 10^5$。

分析

有些题解关于排列解释的不清楚（不能保证不存在两种本质相同的排列），这里用一种更简单的方法解释：

考虑一个点什么时候才可以染色：它的所有祖宗结点没有染过色。

由于不在$x$到根节点路径上的点的染色与$x$的染色情况相互独立，所以我们$x$需要染色的概率就是$\frac{1}{dep_x}$（$dep_1=1$）。

解释一下，我们考虑随机从$x$到根节点的路径上选出一个点，那么选出$x$的概率就是$\frac{1}{dep_x}$（如果没有选出$x$，那么$x$就不能进行染色）。

因为选择$x$对步数的贡献为$1$，所以$x$对步数期望的贡献为$\frac{1}{dep_x}$。

根据期望的可加性，因此$ans=\sum_{x=1}^n E(x)=\sum_{x=1}^n\frac{1}{dep_x}$。

代码

#include<stdio.h>
const int maxn=100005,maxm=200005;
int n,e;
int start[maxn],to[maxm],then[maxm],dep[maxn];
double ans;
inline void add(int x,int y){
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs(int x,int last){
    dep[x]=dep[last]+1;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs(y,x);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        ans+=1.0/dep[i];
    printf("%.20f\n",ans);
    return 0;
}