fork(1) download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <iomanip>
  7. using namespace std;
  8. const int N=100005;
  9. int n;
  10. struct edge{
  11.        int x,y,L;edge *next;
  12.        edge(int x,int y,int L,edge *next):x(x),y(y),L(L),next(next){}
  13. }*ls[N];
  14. int cnt;
  15. int Size[N];
  16. long long Sum[N];
  17. vector <int> QQ[N];
  18.  
  19. bool cmp(int x,int y){
  20.      return Size[y]*Sum[x]<Size[x]*Sum[y];
  21. }
  22.  
  23. long long dfs(int p,int fa){
  24.      long long ret=0;
  25.      vector <int> &Q=QQ[p];
  26.      Q.clear();
  27.      Size[p]=cnt++;
  28.      Sum[p]=0;
  29.      for (edge *t=ls[p];t;t=t->next)
  30.          if (t->y!=fa){
  31.             ret+=dfs(t->y,p);
  32.             ret+=t->L*Size[t->y];
  33.             Q.push_back(t->y);
  34.             Sum[p]+=Sum[t->y]+t->L*2;
  35.             Sum[t->y]+=t->L*2;
  36.          }
  37.      if (!Q.empty()){
  38.           sort(Q.begin(),Q.end(),cmp);
  39.           long long tmp=0;
  40.           for (int i=1;i<Q.size();i++){
  41.               tmp+=Sum[Q[i-1]];
  42.               ret+=tmp*Size[Q[i]];
  43.           }
  44.      }
  45.      Size[p]=cnt-Size[p];
  46.      return ret;
  47. }
  48.  
  49. int main(){
  50.     scanf("%d",&n);
  51.     for (int i=1;i<n;i++){
  52.         int x,y,L;
  53.         scanf("%d%d%d",&x,&y,&L);
  54.         ls[x]=new edge(x,y,L,ls[x]);
  55.         ls[y]=new edge(y,x,L,ls[y]);
  56.     }
  57.     cout << fixed << setprecision(10) << 1.0*dfs(1,0)/(n-1) << endl;
  58. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/UsOfC
language:
C++ (gcc 8.3)
created:
13 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!