fork download
  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
stdin
Standard input is empty
stdout
0.00000000