fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. #define sc(x) scanf("%d",&x)
  5. #define sc2(x,y) scanf("%d%d",&x,&y)
  6. #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  7. #define fi first
  8. #define se second
  9. #define pb(x) push_back(x)
  10. #define mp(x,y) make_pair(x,y)
  11. #define fr(k,n) for(int i=k;i<n;i++)
  12. #define ll long long int
  13. #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  14.  
  15. struct node{
  16. 	double prob,len;
  17. 	int chld,prnt;
  18. 	node(){
  19. 		prob=1;len=0;
  20. 		chld=0;prnt=1;
  21. 	}
  22.  
  23. };
  24.  
  25. vector <pair <int,int> > v;
  26. int n;
  27. struct node rd[100005];
  28.  
  29. int main(){
  30. 	sc(n);
  31. 	int s,t;
  32. 	fr(1,n){
  33. 		sc2(s,t);
  34. 		v.pb(mp(min(s,t),max(s,t)));
  35. 	}
  36. 	sort(v.begin(), v.end());
  37. 	fr(0,n-1){
  38. 		s=v[i].fi;
  39. 		t=v[i].se;
  40. 		rd[s].chld++;
  41. 		rd[t].prnt=s;
  42. 		rd[t].len=rd[s].len+1;
  43. 	}
  44. 	fr(2,n+1){
  45. 		rd[i].prob=(rd[rd[i].prnt].prob / (rd[rd[i].prnt].chld));
  46. 	}
  47. 	double ans=0;
  48.  	fr(1,n+1){
  49. 		if(rd[i].chld==0) ans+=(rd[i].prob*rd[i].len);
  50. 	}
  51. 	printf("%0.8lf\n",ans);
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 5564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.00000000
https://ideone.com/tgm1ro
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!