fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. class Graph
  4. {
  5.     int V;
  6.     list<pair<int,long long int>> *l;
  7.     public:
  8.         Graph(int n)
  9.         {
  10.             V = n;
  11.             l = new list<pair<int,long long int>>[V+1];
  12.         }
  13.     void add_edge(int u,int v,long long int weight)
  14.     {
  15.         l[u].push_back(make_pair(v,weight));
  16.         l[v].push_back(make_pair(u,weight));
  17.     }
  18.     int dfs_helper(int source,bool *visited,int *nodeCount,long long int &ans)
  19.     {
  20.         visited[source] = true;
  21.         nodeCount[source] = 1;
  22.         for(auto itr:l[source])
  23.         {
  24.             if(!visited[itr.first])
  25.             {   nodeCount[source]+=dfs_helper(itr.first,visited,nodeCount,ans);
  26.                 ans+= 2*min(nodeCount[itr.first],V-nodeCount[itr.first])*itr.second;
  27.             }
  28.         }
  29.         return nodeCount[source];
  30.     }
  31.     void dfs()
  32.     {
  33.         bool *visited = new bool[V+1]{0};
  34.         int *nodeCount = new int[V+1]{0};
  35.         long long int ans = 0;
  36.         dfs_helper(1,visited,nodeCount,ans);
  37.         cout<<ans<<endl;
  38.     }
  39. };
  40. int main()
  41. {
  42.     int t;
  43.     cin>>t;
  44.     while(t--)
  45.     {
  46.         int n;
  47.         cin>>n;
  48.         Graph g(n);
  49.         while(n>1)
  50.         {
  51.             n--;
  52.             int i,j;long long int k;
  53.             cin>>i>>j>>k;
  54.             g.add_edge(i,j,k);
  55.         }
  56.         g.dfs();
  57.     }
  58. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
4
1 2 3
2 3 2
3 4 2
stdout
copy 
18
https://ideone.com/kYAXUC
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!