Tietoverkko

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <variant>

#define ull unsigned long long int

std::vector<std::tuple<size_t, size_t, ull>> parse_args() {
    size_t n;
    std::cin >> n;

    auto edges = std::vector<std::tuple<size_t, size_t, ull>>();
    for (size_t i = 0; i < n - 1; ++i) {
        size_t a, b, speed;
        std::cin >> a >> b >> speed;
        edges.push_back(std::make_tuple(--a, --b, speed));
    }

    return edges;
}

int main() {
    auto edges = parse_args();
    auto nodes = std::vector<std::variant<ull, size_t>>(edges.size() + 1, 1ull);
    auto ns = std::vector<size_t>();
    ull total = 0;

    std::sort(edges.begin(), edges.end(), [](auto a, auto b){ return std::get<2>(a) < std::get<2>(b); });

    for (size_t i = edges.size(); i--;) {
        ns.clear();

        size_t a, b;
        ull speed;
        std::tie(a, b, speed) = edges[i];

        size_t* next;
        while ((next = std::get_if<size_t>(&nodes[a]))) {
            ns.push_back(a);
            a = *next;
        }
        while ((next = std::get_if<size_t>(&nodes[b]))) {
            ns.push_back(b);
            b = *next;
        }

        ull a_val = std::get<ull>(nodes[a]);
        ull b_val = std::get<ull>(nodes[b]);
        if (a_val < b_val) {
            std::swap(a, b);
        }

        nodes[a] = a_val + b_val;
        nodes[b] = a;

        for (size_t j = 0; j < ns.size(); ++j) {
            nodes[ns[j]] = a;
        }

        total += a_val * b_val * speed;
    }

    std::cout << total << std::endl;

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED