fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define mod 1000000007
  5. #define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  6. #define point(n) fixed<<setprecision(n)
  7. #define endl '\n'
  8. #define mem(a,val) memset(a,val,sizeof(a))
  9. #define pb push_back 
  10. typedef long long ll;
  11. typedef unsigned long ul;
  12. typedef unsigned long long ull;
  13. typedef pair<int,int> pi;
  14. typedef pair<ll,ll> pll;
  15. #define MOD 1000000000
  16.  
  17. struct pair_hash {
  18.     template <class T1, class T2>
  19.     size_t operator () (const pair<T1,T2> &p) const {
  20.         auto h1 = hash<T1>{}(p.first);
  21.         auto h2 = hash<T2>{}(p.second);
  22.         return h1 ^ h2;  
  23.     }
  24. };
  25.  
  26. class Graph{
  27.     public:
  28.         int n;
  29.         list<int> *adj;
  30.         unordered_map<pair<int,int>,int,pair_hash> mp;
  31.         vector<ll> count;
  32.         bool visited[100001];
  33.         Graph(int n){
  34.             this->n=n;
  35.             adj = new list<int>[n];
  36.             count.resize(n,1);
  37.         }
  38.         void addEdge(int u, int v, int w){
  39.             adj[u].push_back(v);
  40.             adj[v].push_back(u);
  41.             mp[{u,v}] = w;
  42.             mp[{v,u}] = w;
  43.         }
  44.         ll getCountUtil(int node, bool visited[]){
  45.             visited[node]=true;
  46.             for(auto i: adj[node]){
  47.                 if(!visited[i]){
  48.                     count[node] += getCountUtil(i,visited);
  49.                 }
  50.             }
  51.             return count[node];
  52.         }
  53.         void getCount(){
  54.             memset(visited,false,sizeof(visited));
  55.             for(int i=1;i<n;i++){
  56.                 if(!visited[i]){
  57.                     count[i] = getCountUtil(i,visited);
  58.                 }
  59.             }
  60.         }
  61.         ll getAnsUtil(int node, bool visited[]){
  62.             visited[node]=true;
  63.             ll sum=0;
  64.             for(auto i: adj[node]){
  65.                 if(!visited[i]){
  66.                     sum = sum + min(count[i],n-count[i]-1)*mp[{node,i}]*2 + getAnsUtil(i,visited);
  67.                 }
  68.             }
  69.             return sum;
  70.         }
  71.         ll getAns(){
  72.             memset(visited,false,sizeof(visited));
  73.             ll ans = 0; 
  74.             for(int i=1;i<n;i++){
  75.                 if(!visited[i]){
  76.                     ans += getAnsUtil(i,visited);
  77.                 }
  78.             }
  79.             return ans;
  80.         }
  81. };
  82.  
  83. int main()
  84. {
  85.     fastIO
  86.     #ifndef ONLINE_JUDGE
  87.         freopen("input.txt","r",stdin);
  88.         freopen("output.txt","w",stdout);
  89.     #endif
  90.     int t;
  91.     cin>>t;
  92.     for(int j=0;j<t;j++){
  93.         int n;
  94.         cin>>n;
  95.         Graph G(n+1);
  96.         for(int i=0;i<n-1;i++){
  97.             int a,b,c;
  98.             cin>>a>>b>>c;
  99.             G.addEdge(a,b,c);
  100.         }
  101.         G.getCount();
  102.         cout<<"Case #"<<j+1<<": "<<G.getAns()<<endl;
  103.     }
  104.     return 0;
  105. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/EupRVh
problem HOLI, based on SPOJ submission 25741187 (CPP14), 2020-04-11 10:32:34
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!