Tietoverkko

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;



bool sortcol( const vector<ll>& v1,
               const vector<ll>& v2 ) {
 return v1[2] > v2[2];
}

ll id(ll x, vector<ll> edustajat){
    while(x != edustajat[x]) x = edustajat[x];

    return x;
}



int main()
{
    ll n, u, v, w;

    cin >> n;

    vector<vector<ll>> edges;

    vector<ll> edustajat;
    vector<ll> koot;

    edustajat.resize(n+1);
    koot.resize(n+1);

    for (ll i = 0; i < n+1; i++) {
        edustajat[i] = i;
        koot[i] = 1;
    }

    for (ll i = 0; i < n-1; i++) {
        cin >> u >> v >> w;

        vector<ll> e;

        e.push_back(u);
        e.push_back(v);
        e.push_back(w);

        edges.push_back(e);
    }


    sort(edges.begin(), edges.end(), sortcol);

    ll ans = 0;
    ll a, b;

    for (auto x: edges) {
        a = id(x[0], edustajat);
        b = id(x[1], edustajat);

        ans += x[2] * koot[a] * koot[b];

        if (koot[a] > koot[b]){
            swap(a, b);
        }

        edustajat[a] = b;
        koot[b] += koot[a];
    }

    cout << ans << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED