Tietoverkko

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;

#define ll long long
#define ull unsigned long long

struct pair_hash {
    inline ll operator()(const std::pair<ull,ull> & v) const {
        return ((ll)v.first) << 32 | (ll)(ull)v.second;
    }
};

vector<pair<ull, ull>>* vecs[200001] = {};
//map of ulleger, amount
std::unordered_map<ull, unordered_map<ull,ull>*> spds;

ull cur = 0;

void search_tree(ull start, ull spd, ull lst){

    vector<pair<unordered_map<ull,ull>*, ull>> nspds = {};

    unordered_map<ull,ull> loneSpds = {};

    for (const auto &item : *vecs[start]){
        if(item.first == lst) continue;
        if(vecs[item.first]->size() > 1){
            search_tree(item.first, item.second, start);
            nspds.emplace_back(spds[item.first], item.first);
        }else{
            const auto iter = loneSpds.find(item.second);
            ull val = 1;
            if(iter != loneSpds.end()) {
                val += iter->second;
                iter->second = val;
            } else
                loneSpds.emplace(item.second, val);
        }

    }

    for (const auto &item : nspds){
        for (const auto &item2 : *item.first){
            for (const auto &item3 : loneSpds){
                ull tmp = min(item3.first, item2.first);
                cur += tmp*(item3.second * item2.second);
            }
        }
    }

    for (const auto &item : *vecs[start]){
        if(item.first == lst || vecs[item.first]->size() == 1) continue;
        for (const auto &item2 : nspds){
            if(item2.second == item.first){
                continue;
            }
            for (const auto &item3 : *item2.first){
                ull tmp = min(item.second, item3.first);
                cur += tmp*(item3.second);
            }
        }
        const auto iter = loneSpds.find(item.second);
        ull val = 1;
        if(iter != loneSpds.end()) {
            val += iter->second;
            iter->second = val;
        } else
            loneSpds.emplace(item.second, val);
    }


    auto* ret_spds = new unordered_map<ull,ull>();
    //test
    auto loopNspds = nspds;
    for (auto iter = loopNspds.begin(); iter != loopNspds.end(); ) {

        for (const auto &nspd2 : loopNspds){
            if(&*iter == &nspd2) continue;
            for (const auto &item : *iter->first){
                for (const auto &item2 : *nspd2.first){
                    ull tmp = min(item.first, item2.first);
                    cur += tmp*(item.second * item2.second);
                }
            }
        }

        for (const auto &item : *iter->first){
            ull retSpd = min(spd, item.first);
            const auto iter2 = ret_spds->find(retSpd);
            ull val = item.second;
            if(iter2 != ret_spds->end()) {
                val += iter2->second;
                iter2->second = val;
            } else
                ret_spds->emplace(retSpd, val);
        }
        iter = loopNspds.erase(iter);
    }

    for (const auto &item : nspds){
        for (const auto &item2 : *item.first){
            cur += item2.first * item2.second;
        }
    }

    //add all spds to loneSpds and spds between loneSpds in the same pair
    unordered_map<ull, ull> nLoneSpds = {};
    for (const auto &item : loneSpds){
        cur += item.first*item.second;
        ull am = item.second -1;
        cur += item.first*am;
    }
    //
    for (auto iter = loneSpds.begin(); iter != loneSpds.end(); ) {
        auto item = *iter;
        for (const auto &item2 : loneSpds){
            if(&item2 == &*iter) continue;
            ull tmp = min(item.first, item2.first);
            cur += tmp*((item.second) * item2.second);
        }

        if(start != 1){
            //push loneSpds to nSpds
            ull nspd = min(item.first, spd);
            const auto iter2 = nLoneSpds.find(nspd);
            ull amount = item.second;
            if(iter2 != nLoneSpds.end()){
                amount += iter2->second;
                iter2->second = amount;
            }else{
                nLoneSpds.emplace(nspd, amount);
            }
        }

        iter = loneSpds.erase(iter);
    }

    for (const auto &item : nLoneSpds){
        const auto iter = ret_spds->find(item.first);
        ull val = item.second;
        if(iter != ret_spds->end()) {
            val += iter->second;
            iter->second = val;
        } else
            ret_spds->emplace(item.first, val);
    }

    spds[start] = ret_spds;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ull n;
    cin >> n;

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

        if(vecs[a] == nullptr) {
            vecs[a] = new vector<pair<ull, ull>>();
        }
        if(vecs[b] == nullptr) {
            vecs[b] = new vector<pair<ull, ull>>();
        }

        vecs[a]->emplace_back(make_pair(b,x));
        vecs[b]->emplace_back(make_pair(a,x));
    }

    search_tree(1, __INT32_MAX__, -1);

    cout << cur;
    flush(std::cout);
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED