Tietoverkko

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

vector<pair<ll, pair<int, int>>> edges;

int rep[200001];
int sz[200001];

int id(int x) {
    while (rep[x] != x) x = rep[x];
    return x;
} 

void join(int a, int b) {
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    rep[b] = a;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({c, { a, b }});
    }

    for (int i = 1; i <= n; ++i) {
        sz[i] = 1;
        rep[i] = i;
    }

    sort(edges.rbegin(), edges.rend());

    ll ans = 0;

    for (auto p : edges) {
        ll w = p.first;
        int a = p.second.first;
        int b = p.second.second;
        a = id(a);
        b = id(b);
        ans += sz[a] * sz[b] * w;
        join(a, b);
    }

    cout << ans << "\n";

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED