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);
}