Tietoverkko

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

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

vector<pair<int, int>>* vecs[200001] = {};
//map of integer, amount
std::unordered_map<int, vector<unordered_map<int,int>>> spds;
bitset<200000> visited = {};

ull cur = 0;

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

    vector<unordered_map<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){
            search_tree(item.first, item.second, start);
            vector<unordered_map<int,int>> spdVec = spds[item.first];
            for (const auto &item2 : spdVec){
                unordered_map<int,int> nMap = {};
                for (const auto &item3 : item2){
                    //take slower of speed to next node, and the node after that
                    int spd2 = min(item3.first, item.second);
                    int amount = item3.second;
                    auto iter2 = nMap.find(spd2);
                    if(iter2 != nMap.end()) amount += iter2->second;
                    nMap.emplace_hint(iter2, spd2, amount);
                }
                nspds.insert(nspds.end(), nMap);
            }
        }
        auto iter = loneSpds.find(item.second);
        int val = 0;
        if(iter != loneSpds.end()) val = iter->second;
        val++;
        loneSpds.emplace_hint(iter, item.second, val);
    }

    //TODO: combine spds when returning
    for (const auto &nspd1 : nspds){
        for (const auto &nspd2 : nspds){
            if(&nspd1 == &nspd2) continue;
            for (const auto &item : nspd1){
                for (const auto &item2 : nspd2){
                    int tmp = min(item.first, item2.first);
                    cur += tmp*(item.second + item2.second);
                }
            }
        }
    }
    for (const auto &item : nspds){
        for (const auto &item2 : item){
            cur += item2.first * item2.second;
        }
    }


    unordered_map<int, int> nLoneSpds = {};
    for (const auto &item : loneSpds){
        cur += item.first*item.second;
    }

    for (auto iter = loneSpds.begin(); iter != loneSpds.end(); ) {
        auto item = *iter;
        for (const auto &item2 : loneSpds){
            if(&item2 == &*iter) continue;
            int tmp = min(item.first, item2.first);
            cur += tmp*(item.second +item2.second - 1);
        }

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

        iter = loneSpds.erase(iter);
    }

    nspds.insert(nspds.end(), nLoneSpds);

    spds[start] = nspds;
}

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

    int n;
    cin >> n;

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

        vector<pair<int, int>>* newv;
        if(vecs[a] == nullptr) {
            newv = new auto(vector<pair<int, int>>());
            vecs[a] = newv;
        }
        if(vecs[b] == nullptr) {
            newv = new auto(vector<pair<int, int>>());
            vecs[b] = newv;
        }


        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: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: WRONG ANSWER

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED