fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/paf6cf
language:
C++14 (gcc 8.3)
created:
6 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!