CF280C Game on Tree（期望的線性性）

題目

給出一棵樹，每次随機等機率選擇一未染黑的點，将它及其子樹染黑。問期望多少次操作可以将樹全部染黑。

n < = 1 e 5 n<=1e5 n<=1e5

期望操作次數 -> 每個點的期望操作次數之和 -> 每個點被操作的機率之和 -> ∑ i 1 d e p i \sum_{i} \frac 1{dep_i} ∑i​depi​1​

我真的沒有在水部落格。

A C   C o d e \rm AC \ Code AC Code

#include<bits/stdc++.h>
#define maxn 100005
#define pb push_back
using namespace std;

int n;
vector<int>G[maxn];
double ans;

void dfs(int u,int ff,int d){
	ans += 1.0 / d;
	for(int v:G[u]) if(v!=ff) dfs(v,u,d+1);
}

int main(){
	scanf("%d",&n);
	for( int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),G[u].pb(v),G[v].pb(u);
	dfs(1,0,1);
	printf("%.10lf\n",ans);
}