Tietoverkko

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define N 200001

int n;
ll r;
set<int> v[N];
int c[N];
set<pair<ll,pair<int,int>>> s;

void nodecount(int a, int e)
{
    c[a] = 1;
    for(auto u : v[a])
    {
        if(u == e) continue;
        nodecount(u, a);
        c[a] += c[u];
    }
}

int main()
{
    cin>>n;
    int a,b;
    ll x;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b>>x;
        v[a].insert(b);
        v[b].insert(a);
        s.insert(make_pair(x,make_pair(a,b)));
    }
    for(auto p : s)
    {
        int a = p.second.first;
        int b = p.second.second;
        ll x = p.first;
        v[a].erase(b);
        v[b].erase(a);
        nodecount(a, 0);
        nodecount(b, 0);
        r += x * c[a] * c[b];
    }
    cout<<r;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED