Tietoverkko

using namespace std;
#include <iostream>
#include <vector>
#include <map>

#define ll long long

vector<pair<ll,ll>> c[200001];
pair<ll,ll> p[200001];
ll d[200001];
map<pair<ll, ll>, ll> m;
ll ans = 0;

void haku(ll n, ll k, ll s)
{
	if (n != k)
	{
		m[{n, k}] = s;
		ans += s;
		d[k]++; d[n]++;
	}
	for (auto i : c[k])
	{
		if (i.second < s)haku(n, i.first, i.second);
		else haku(n, i.first, s);
	}
}

int main()
{
	ll n;
	cin >> n;
	for (ll i = 1; i < n; i++)
	{
		ll a, b, x;
		cin >> a >> b >> x;
		c[a].push_back({ b,x });
		p[b] = { a,x };
	}
	for (ll i = 1; i <= n; i++)
		haku(i, i, 1e9);
	for (ll i = 1; i <= n; i++)
	{
		if (d[i] != n-1)
		{
			for (ll j = 1; j <= n; j++)
			{
				if (j != i && !m.count({ i,j }) && !m.count({ j,i }))
				{
					if (p[i].second < m[{p[i].first, j}])m[{i, j}] = p[i].second;
					else m[{i, j}] = m[{p[i].first, j}];
					ans += m[{i, j}];
					d[i]++; d[j]++;
				}
			}
		}
	}
	cout << ans;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED