CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:Totska
Submission time:2021-10-12 10:20:19 +0300
Language:PyPy3
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
Test results
testverdicttimegroup
#1ACCEPTED0.04 s1, 2, 3details
#2ACCEPTED0.14 s2, 3details
#3--3details

Code

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 details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
1103702320243776

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)