Tietoverkko

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define N 200001

int n;
ll r;
vector<pair<ll,pair<int,int>>> s;
pair<bool,ll> v[N];

int main()
{
    cin>>n;
    int a,b;
    ll x;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>x;
        s.push_back(make_pair(x,make_pair(a,b)));
        v[i] = make_pair(false, 1);
    }
    v[n] = make_pair(false, 1);
    sort(s.rbegin(), s.rend());
    for(auto p : s)
    {
        int a = p.second.first;
        int b = p.second.second;
        ll x = p.first;
        int la=0;
        while(v[a].first)
        {
            a = v[a].second;
            la++;
        }
        int lb=0;
        while(v[b].first)
        {
            b = v[b].second;
            lb++;
        }
        r += x * v[a].second * v[b].second;
        if(la>lb)
        {
            v[a].second += v[b].second;
            v[b].first = true;
            v[b].second = a;
        }
        else
        {
            v[b].second += v[a].second;
            v[a].first = true;
            v[a].second = b;
        }
    }
    cout<<r;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED