Tietoverkko

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int edustaja(int verkko[], int a)
{
    // cout << "Edustajaa solmulle " << a << "\n";
    // cout << "    " << verkko[a] << "\n";
    while (a != verkko[a])
        a = verkko[a];
    // cout << "    Edustaja löytyi " << verkko[a] << "\n";
    return a;
}

bool sama(int verkko[], int a, int b)
{
    return edustaja(verkko, a) == edustaja(verkko, b);
}

void yhdista(int verkko[], int koko[], int a, int b)
{
    // a = edustaja(verkko, a);
    // b = edustaja(verkko, b);
    if (koko[a] < koko[b])
    {
        int c = a;
        a = b;
        b = c;
    }
    verkko[b] = a;
    koko[a] += koko[b];
}

int main()
{
    int n;
    cin >> n;

    vector<pair<int, pair<int, int>>> kaaret;

    int koko[n + 1];
    int verkko[n + 1];

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, x;
        cin >> a >> b >> x;

        kaaret.push_back({x, {a, b}});

        koko[i + 1] = 1;
        verkko[i + 1] = i + 1;
    }
    koko[n] = 1;
    verkko[n] = n;

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

    long tulos = 0;

    for (auto kaari : kaaret)
    {

        int a = edustaja(verkko, kaari.second.first);
        int b = edustaja(verkko, kaari.second.second);

        // cout << "Alkusolmu " << kaari.second.first << "  loppusolmu " << kaari.second.second << "\n";
        // cout << "Lisätään " << (koko[a] * koko[b] * kaari.first) << "\n";

        tulos += (long)koko[a] * (long)koko[b] * (long)kaari.first;

        yhdista(verkko, koko, a, b);
    }

    cout << tulos << "\n";
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED