Tietoverkko

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

vector<pair<int, pair<int,int>>> network;
map<int, int> lookupTable; 
map<int, set<int>> graph;

long long search(int node, int ignoredNode) {
    if (graph[node].size() <= 1) {
        return 1;
    }
    long long s = 1;

    for (auto n : graph[node]) {
        if (n == ignoredNode) {
            continue;
        }
        s += search(n, node);
    }
    return s;
}

int main() {
    int n, a, b, d;
    long long s = 0;

    cin >> n;
    for (int i=1; i<n; i++) {
        graph[i] = set<int>();
    }
    for (int i=0; i<n-1; i++) {
        cin >> a >> b >> d;
        graph[a].insert(b);
        graph[b].insert(a);
        network.push_back(pair<int, pair<int,int>>(d, pair<int,int>(a,b)));
    }
    sort(network.begin(), network.end());


    long long l, r;
    // lookupTable[a]
    lookupTable[network[0].second.first] = n;
    for (auto edge: network) {
        l = 1, r = 1;
        d = edge.first;
        a = edge.second.first, b = edge.second.second;
        graph[a].erase(b);
        graph[b].erase(a);
        if (lookupTable.count(a)) {
            for (auto node: graph[a])
                l += search(node, a);
            r = lookupTable[a] - l;
        } else if (lookupTable.count(b)) {
           for (auto node: graph[b])
                l += search(node, b);
            r = lookupTable[b] - l; 
        } else {
            for (auto node: graph[a])
                l += search(node, a);
            for (auto node: graph[b])
                l += search(node, b);
        }
        
        lookupTable[a] = l;
        lookupTable[b] = r;
        // for (auto node: graph[b]) {
        //     r += search(node, b);
        // }
        s += l*r*d;
    }
    cout << s;
}

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