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<const int, int>>* vecs[200001] = {};
//map of ulleger, amount
ull cur = 0;

unordered_map<int,int>* search_tree(const int start, const int spd, const int lst){
    vector<pair<const unordered_map<int,int>*, int>> nspds = {};

    unordered_map<int,int> loneSpds = {};

    for (const auto &item : *vecs[start]){
        if(item.first == lst) continue;
        if(vecs[item.first]->size() > 1){
            nspds.emplace_back(search_tree(item.first, item.second, start), 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){
            cur += item2.first * (ull) item2.second;
            for (const auto &item3 : loneSpds){
                const 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<int,int>();
    //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){
                    cur += min(item.first, item2.first)*(item.second * (ull)item2.second);
                }
            }
        }

        if(start != 1){
            for (const auto &item : *iter->first){
                const 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);
    }

    //add all spds to loneSpds and spds between loneSpds in the same pair
    unordered_map<int, int> nLoneSpds = {};
    for (const auto &item : loneSpds){
        cur += (ull) item.first*item.second;
        const 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;
            const ull tmp = min(item.first, item2.first);
            cur += tmp*((item.second) * item2.second);
        }

        if(start != 1){
            //push loneSpds to nSpds
            const 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);
    }

    return 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<const int, int>>();
        }
        if(vecs[b] == nullptr) {
            vecs[b] = new vector<pair<const int, int>>();
        }

        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