fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<unordered_set>
  3. using namespace std;
  4.  #define fio ios_base::sync_with_stdio(false)
  5.  
  6. #define ll long long int
  7.  
  8. #define s(x) scanf("%lld",&x)
  9. #define s2(x,y) s(x)+s(y)
  10. #define s3(x,y,z) s(x)+s(y)+s(z)
  11.  
  12. #define p(x) printf("%lld\n",x)
  13. #define p2(x,y) p(x)+p(y)
  14. #define p3(x,y,z) p(x)+p(y)+p(z)
  15. #define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
  16. #define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
  17.  
  18. #define ff first
  19. #define ss second
  20. #define mp(x,y) make_pair(x,y)
  21. #define pll pair<ll,ll>
  22. #define pb push_back
  23.  
  24. ll inf = 1e18;
  25. ll mod = 1e9 + 7 ;
  26. ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b);}
  27.  
  28.  
  29.  
  30. vector<pll>adj[100005];
  31.  
  32. // ret will contain the total travel distance (travelled one-sidedly) by the visitors , 
  33. // that's why at the end we are multiplying by 2 as people from both sides are crossing 
  34. // a particular edge.
  35. ll ret=0;
  36. ll n;
  37.  
  38. ll dfs(ll par, ll u){
  39.   ll ans=1;
  40.   for(ll i=0;i<adj[u].size();i++){
  41.     ll v = adj[u][i].first;
  42.     ll wt = adj[u][i].second;
  43.  
  44.     if(v==par)continue;
  45.  
  46.     // nodes will contain the total number of nodes present in the tree subrooted at child 'v'
  47.     ll nodes = dfs(u,v);
  48.     ret+=2*min(nodes,n-nodes)*wt;
  49.     ans+=nodes;
  50.   }
  51.   // ans contains the total number of nodes present in the tree subrooted at node 'u'
  52.   return ans;
  53. }
  54.  
  55. int main()
  56. {
  57.   // freopen("input.txt","r",stdin);
  58.    // freopen("output.txt","w",stdout);
  59.   ll t=1;
  60.   s(t);
  61.   ll tc=1;
  62.   while(t--){
  63.     ret=0;
  64.     s(n);
  65.     F(i,1,n)adj[i].clear();
  66.  
  67.     F(i,1,n-1){
  68.       ll u,v,x;
  69.       s3(u,v,x);
  70.       adj[u].pb({v,x});
  71.       adj[v].pb({u,x});
  72.     }
  73.  
  74.     dfs(-1,1);
  75.     cout<<"Case #"<<tc++<<": "<<ret<<endl;
  76.   }
  77. }
Success #stdin #stdout 0s 6024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case #1: 0
https://ideone.com/8jehdN
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!