题意
给出一棵含 \(n\) 个白点的有根树,每次随机选择一个还没有被染黑的节点,将这个节点和这个节点子树中的所有点染黑。
问期望操作多少次后所有点都被染黑。
分析
由题意可得，如果一个节点的祖先被选中了，那么这个节点就已经被染黑了，不会再被选中。
因此对于每个节点，只考虑这个节点和它的所有祖先，其他点的选中并不会影响该点被选中的概率，相当于我们不断地选择，直到选中了这个点或者它的某一个祖先时，这个点才会被染色。
总结一下，如果某一点有 \(x\) 个祖先，那么这 \((x+1)\) 个点中，每个点最先被选出的概率是相等的。
所以我们 \(dfs\) 求出每个点的深度即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n,head[100005],tot;
double ans;
struct node{
int to,next;
}a[200005];
void dfs(int u,int fr,int dep){
ans+=1.0/dep;
for(int i=head[u];i;i=a[i].next){
int v=a[i].to;
if(v==fr)continue;
dfs(v,u,dep+1);
}
}
void add(int q,int m){
a[++tot].to=m;
a[tot].next=head[q];
head[q]=tot;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,0,1);
printf("%.8lf",ans);
return 0;
}