Tietoverkko

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

using namespace std;

vector<struct yhteys> yhteydet;
vector<uint64_t> naapurit[200000];

struct yhteys {
    uint64_t a;
    uint64_t b;
    uint64_t nopeus;
    bool kayty;
};

bool a_comp(struct yhteys a, struct yhteys b)
{
    return a.nopeus < b.nopeus;
}

uint64_t maara(uint64_t tietokone, uint64_t pois)
{
    /*uint64_t m = 1;
    for(uint64_t naapuri: naapurit[tietokone]) {
        //cout << tietokone << ": " << naapuri << endl;
        //cout << "MÄÄRÄ " << tietokone << " " << pois << " " << naapuri << endl;
        if(naapuri != pois && naapuri != 0xffffffffffffffff) {
            //cout << "OIKEA NAAPURI" << endl;
            m += maara(naapuri, tietokone);
        }
    }
    return m;*/
    uint64_t m = 0;
    stack<int> tietokoneet, poiss;
    tietokoneet.push(tietokone);
    poiss.push(pois);
    while(!tietokoneet.empty()) {
        tietokone = tietokoneet.top();
        pois = poiss.top();
        tietokoneet.pop();
        poiss.pop();

        m++;
        for(uint64_t naapuri: naapurit[tietokone]) {
            if(naapuri != pois && naapuri != 0xffffffffffffffff) {
                tietokoneet.push(naapuri);
                poiss.push(tietokone);
            }
        }
    }

    return m;
}

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

    for(uint64_t i = 0; i < n - 1; i++) {
        struct yhteys yhteys;
        cin >> yhteys.a >> yhteys.b >> yhteys.nopeus;
        yhteys.kayty = false;
        yhteydet.push_back(yhteys);
        naapurit[yhteys.a].push_back(yhteys.b);
        naapurit[yhteys.b].push_back(yhteys.a);
    }

    sort(yhteydet.begin(), yhteydet.end(), a_comp);

    uint64_t summa = 0;
    for(struct yhteys yhteys: yhteydet) {
        uint64_t m1 = maara(yhteys.b, yhteys.a);

        //remove(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a);
        //remove(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b);
        naapurit[yhteys.b][distance(naapurit[yhteys.b].begin(), find(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a))] = 0xffffffffffffffff;
        naapurit[yhteys.a][distance(naapurit[yhteys.a].begin(), find(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b))] = 0xffffffffffffffff;

        //cout << "A" << yhteys.nopeus << " " << yhteys.b << " " << yhteys.a << " " << r << endl;
        uint64_t m2 = (maara(yhteys.a, yhteys.b) - 1);
        uint64_t r = m1 * (m2 + 1) * yhteys.nopeus;
        //cout << "A" << yhteys.nopeus << " " << yhteys.a << " " << yhteys.b << " " << r << endl;
        summa += r;
    }

    cout << summa << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: RUNTIME ERROR