fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. map<ll,ll>mp1;
  5. ll ans,n,t,x,y,z;;
  6. ll dfs(map<ll,map<ll,ll> >mp,map<ll,bool>&v,ll node)
  7. {
  8.  
  9.     v[node]=true;
  10.     map<ll,map<ll,ll> > :: iterator out;
  11.     for(out=mp.begin();out!=mp.end();out++)
  12.     if(out->first == node )
  13.     break;
  14.       map<ll,ll>  :: iterator in;
  15.       mp1[node]=1;
  16.       for(in=out->second.begin();in!=out->second.end();in++)
  17.       {
  18.           if(!v[in->first])
  19.           {
  20.             mp1[node]+=dfs(mp,v,in->first);
  21.             ll p=mp1[in->first];
  22.             ans+=min(p,n-p)*2*(in->second);
  23.           }
  24.       }
  25.       return mp1[node] ;
  26. }
  27. int main()
  28. {
  29.   cin>>t;
  30.   while(t--)
  31.   {
  32.       cin>>n;
  33.       ans=0;
  34.   //    cout<<n<<endl;
  35.       map<ll,map<ll,ll> >mp;
  36.       map<ll,bool>v;
  37.       v[n]=false;
  38.       for(int i=0;i<n-1;i++)
  39.       {
  40.           cin>>x>>y>>z;
  41.           mp[x][y]=z;
  42.           mp[y][x]=z;
  43.           v[i+1]=false;
  44.       }
  45.       ll k=dfs(mp,v,1);
  46.       cout<<ans<<endl;
  47.       mp1.clear();
  48.   }
  49. }
  50.  
Success #stdin #stdout 0s 4520KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/DkVjBr
problem HOLI, based on SPOJ submission 25268796 (CPP14), 2020-01-20 01:46:26
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!