Tietoverkko

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

struct UF {
	vector<int> p;

	UF(int n) : p(n, -1) {}

	int root(int s) {
		return p[s] < 0 ? s : p[s] = root(p[s]);
	}

	int sz(int s) {
		return -p[root(s)];
	}

	void join(int a, int b) {
		a = root(a);
		b = root(b);
		p[b] += p[a];
		p[a] = b;
	}
};

int main() {
	int n;
	cin >> n;

	vector<tuple<int, int, int>> e;

	for (int i = 0; i < n - 1; ++i) {
		int a, b, x;
		cin >> a >> b >> x;
		e.emplace_back(x, a - 1, b - 1);
	}

	sort(e.rbegin(), e.rend());

	long r = 0;
	UF uf(n);

	for (auto [x, a, b] : e) {
		r += 1ll * x * uf.sz(a) * uf.sz(b);
		uf.join(a, b);
	}

	cout << r << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED