CF280C-Game on Tree【數學期望】

正題

題目連結:https://www.luogu.com.cn/problem/CF280C

題目大意

\(n\)個點的一棵樹，每次選擇一個沒有染色的點把它和它的子樹染黑，求期望全部染黑的步數。

解題思路

可以了解為我們按照一個順序輪流染色，如果一個點有祖先節點在它前面就不用計算貢獻。

也就是如果一個點要計算貢獻的機率就是它要排在所有它的祖先節點前面，也就是\(\frac{1}{dep_x}\)。求個和就好了。

時間複雜度\(O(n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e5+10;
int n;double ans;
vector<int> G[N];
void dfs(int x,int fa,int dep){
    for(int i=0;i<G[x].size();i++){
        int y=G[x][i];
        if(y==fa)continue;
        dfs(y,x,dep+1);
    }
    ans+=1.0/(double)dep;
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,0,1);
    printf("%.10lf\n",ans);
}