题目链接在这里：Problem - F - Codeforces
由于期望的可加性，我们可以单独考虑每一个点对整体期望的贡献值，对于一个点，如果它被删掉了，一定是从根节点到它本身这条路径上有点被删了，我们考虑的是这个点对整体的贡献，所以假设它的深度为d，贡献值即为1*(1/d)+0*((d-1)/d)，花见一下就是1/d
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=1e5+5; 4 int n,cnt,d[MAX],num[MAX],nu; 5 vector <int> adj[MAX]; 6 double f[MAX],ans; 7 int main(){ 8 freopen ("f.in","r",stdin); 9 freopen ("f.out","w",stdout); 10 int i,j,u,v,zt,now; 11 vector <int> x; 12 scanf("%d",&n); 13 for (i=1;i<n;i++){ 14 scanf("%d%d",&u,&v); 15 adj[u].push_back(v); 16 adj[v].push_back(u); 17 } 18 queue <int> q; 19 while (!q.empty()) q.pop(); 20 q.push(1);now=1; 21 memset(f,0,sizeof(f)); 22 f[1]=1; 23 while (!q.empty()){ 24 zt=q.front();q.pop(); 25 for (i=1;i<=adj[zt].size();i++) 26 f[now+i]=1.0/(double)(now+i)+(double)(f[now+i-1]+1)*(double)(i)/(double)(now+i); 27 now+=adj[zt].size(); 28 } 29 memset(d,0,sizeof(d)); 30 d[1]=1;q.push(1); 31 memset(num,0,sizeof(num)); 32 nu=0; 33 while (!q.empty()){ 34 zt=q.front();q.pop(); 35 nu=max(nu,d[zt]); 36 num[d[zt]]++; 37 //cout<<zt<<' '<<d[zt]<<' '<<num[d[zt]]<<endl; 38 for (i=0;i<adj[zt].size();i++){ 39 if (d[adj[zt][i]]!=0) continue; 40 d[adj[zt][i]]=d[zt]+1; 41 q.push(adj[zt][i]); 42 //cout<<"fuck "<<zt<<' '<<adj[zt][i]<<endl; 43 } 44 } 45 //cout<<nu<<endl; 46 for (i=1;i<=nu;i++){ 47 //cout<<num[i]<<' '; 48 ans+=(double)num[i]/(double)i; 49 }//cout<<endl; 50 printf("%.8lf",ans); 51 return 0; 52 }