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){
    //TODO: doesnt work with multiple same spds

    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 --NOTE--: we dont need to check the minimum speed here, bcs its already checked @ line 95
                    int spd2 = min(item3.first, item.second);
                    int amount = item3.second;
                    auto iter2 = nMap.find(spd2);
                    if(iter2 != nMap.end()) {
                        amount += iter2->second;
                        iter2->second = amount;
                    }else
                        nMap.emplace(spd2, amount);
                }*/
                nspds.insert(nspds.end(), item2);
            }
        }else{
            auto iter = loneSpds.find(item.second);
            int 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){
            for (const auto &item3 : loneSpds){
                int tmp = min(item3.first, item2.first);
                cur += tmp*(item3.second +item2.second - 1);
            }
        }
    }

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


    unordered_map<int,int> ret_spds = {};
    //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 : nspd1){
            auto iter = ret_spds.find(item.first);
            int val = item.second;
            if(iter != ret_spds.end()) {
                val += iter->second;
                iter->second = val;
            } else
                ret_spds.emplace(item.first, val);
        }
    }

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

    //TODO: lonespds * nspds

    //TODO: remove spd between child with children and that child's children from the sum
    /*for (const auto &item : nspds){
        for (const auto &item2 : item){
            for (const auto &item3 : loneSpds){
                int tmp = min(item3.first, item2.first);
                cur += tmp*(item3.second +item2.second - 1);
            }
        }
    }*/

    //add all spds to loneSpds and spds between loneSpds in the same pair
    unordered_map<int, int> nLoneSpds = {};
    for (const auto &item : loneSpds){
        cur += item.first*item.second;
        int 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;
            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 = 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){
        auto iter = ret_spds.find(item.first);
        int val = item.second;
        if(iter != ret_spds.end()) {
            val += iter->second;
            iter->second = val;
        } else
            ret_spds.emplace(item.first, val);
    }

    vector<unordered_map<int,int>> retSpdVec = {ret_spds};

    spds[start] = retSpdVec;
}

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