fork download
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. ///////////////////////////////////Nikhil Srivastava////////////////////////////////////////
  5. ///////////////////////////////////IIT Jodhpur//////////////////////////////////////////////
  6. ///////////////////////////////////Bazinga//////////////////////////////////////////////////
  7. #define SPEED ios::sync_with_stdio(false); cin.tie(0)
  8. #define sci(a) scanf("%d",&a)
  9. #define scl(a) scanf("%I64d",&a)
  10. #define scc(a) scanf("%c",&a)
  11. #define scf(a) scanf("%f",&a)
  12. #define scd(a) scanf("%lf",&a)
  13. #define scs(a) scanf("%s",&a)
  14. #define printi(x) printf("%d\n",x)
  15. #define printl(x) printf("%lld\n",x)
  16. #define loop(i,a,n) for(int i=a;i<n;++i)
  17. #define loopd(i,a,n) for(int i=a;i>=n;--i)
  18. #define nl printf("\n");
  19. #define ll long long int
  20. #define mp(a,b) make_pair(a,b)
  21. #define pi pair < int,int >
  22. #define pl pair < ll,ll >
  23. #define pb push_back
  24. #define maxi 100005
  25. #define MOD (1000000007LL)
  26. #define INF 1e18
  27. #define MAXI 1000005
  28. #define ff first
  29. #define ss second
  30. static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  31. static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  32. ll power(ll base, ll p){
  33. ll ans = 1;while(p){if(p&1)ans=(ans*base);base=(base*base);p/=2;}return ans;
  34. }
  35.  
  36. ll modPower(ll base, ll p, ll mod = MOD){
  37. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  38. }
  39.  
  40. ll gcd(ll a, ll b){
  41. if(b == 0) return a;
  42. return gcd(b, a%b);
  43. }
  44. /////////////////////////////////////////////Solution From Here//////////////////////////////////////////////////////////
  45.  
  46.  
  47. vector<int> adj[MAXI];
  48. bool vis[MAXI];
  49. ll d[MAXI];
  50. long double prob[MAXI];
  51.  
  52. void bfs(int s)
  53. {
  54. memset(d,0,sizeof(d));
  55. memset(vis,false,sizeof(vis));
  56. deque<int> q;
  57. vis[s] = 1;
  58. d[s] = 0;
  59. prob[s] = 1.0;
  60. q.pb(s);
  61. while(!q.empty()) {
  62. int u = q.front();
  63. q.pop_front();
  64.  
  65. for(int i=0;i<adj[u].size();++i) {
  66. if(!vis[adj[u][i]]) {
  67. vis[adj[u][i]] = 1;
  68. d[adj[u][i]] = d[u] + 1;
  69. if(u!=1)prob[adj[u][i]] = prob[u]*(1.0/(long double)(adj[u].size()-1));
  70. else prob[adj[u][i]] = prob[u]*(1.0/(long double)(adj[u].size()));
  71. q.pb(adj[u][i]);
  72. }
  73. }
  74.  
  75. }
  76. }
  77.  
  78.  
  79.  
  80. int main()
  81. {
  82.  
  83. SPEED;
  84. int n;
  85. cin>>n;
  86. loop(i,1,n) {
  87. int u,v;
  88. cin>>u>>v;
  89. adj[u].pb(v);
  90. adj[v].pb(u);
  91. }
  92. if(n == 1)
  93. {
  94. cout<<"0";
  95. return 0;
  96. }
  97. vector<int> ans;
  98. ans.clear();
  99. loop(i,2,n+1) {
  100. if(adj[i].size() == 1)
  101. ans.pb(i);
  102. }
  103. bfs(1);
  104. long double dd = 0.0;
  105. loop(i,0,ans.size()) {
  106.  
  107. dd += d[ans[i]]*prob[ans[i]];
  108.  
  109. }
  110. // cout<<dd;
  111.  
  112. // long double a = (dd)/(long double)ans.size();
  113.  
  114. cout<<setprecision(20)<<dd;
  115.  
  116.  
  117. }
  118.  
  119.  
Time limit exceeded #stdin #stdout 5s 4259840KB
stdin
Standard input is empty
stdout

Standard output is empty