• 周四. 8月 11th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day14 F (树上期望)

admin

11月 28, 2021

题目链接在这里: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 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表评论

您的电子邮箱地址不会被公开。