Tietoverkko

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

vector<pair<int, ll>> v[200001];
ll ans[200001];

void dfs(int s, int e, ll mn, int from) {
    if (s != from) ans[from] += mn;
    for (auto[u, w] : v[s]) {
        if (u == e) continue;
        dfs(u, s, min(mn, w), from);
    }
}
 
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, c;
        cin >> a >> b >> c;
        v[a].push_back({b, (ll)c});
        v[b].push_back({a, (ll)c});
    }

    ll sum = 0;

    for (int i = 1; i <= n; ++i) {
        dfs(i, -1, 1e9, i);
        sum += ans[i];
    }

    cout << sum / 2 << "\n";

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED