Tietoverkko

from operator import itemgetter
n = int(input())

edges = []
for _ in range(n-1):
    edges.append(tuple(map(int, [x for x in input().split()])))

edges.sort(key=itemgetter(2), reverse=True)

edustajat = [i for i in range(n+1)]
koot = [1 for _ in range(n+1)]

def id(x):
    path = set()

    while x != edustajat[x]:
        path.add(x)
        x = edustajat[x]

    for p in path:
        edustajat[p] = x

    return x

ans = 0
for u, v, w in edges:
    a = id(u)
    b = id(v)

    ans += w * koot[a] * koot[b]

    if koot[a] > koot[b]:
        a, b = b, a

    edustajat[a] = b
    koot[b] += koot[a]

print(ans)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED