Tietoverkko

from operator import itemgetter
from math import factorial as fc
from copy import deepcopy
n = int(input())

edges = []
z = set()
for i in range(n-1):
    edges.append(tuple(map(int, input().split())))
    z.add(edges[i][2])

edges.sort(key=itemgetter(2))

speeds = {x: [] for x in z}

complist = [-1 for i in range(n+1)]

for e in edges:
    speeds[e[2]].append((e[0], e[1]))

# print(edges)
# print(speeds)


def dfs(node):
    if node in visited:
        return

    comp.add(node)
    visited.add(node)

    for nb in adj[node]:
        dfs(nb)


def gendict(edges):
    nodes = {e[0] for e in edges} | {e[1] for e in edges}

    adj = {e: [] for e in nodes}
    for e in edges:
        adj[e[0]].append(e[1])
        adj[e[1]].append(e[0])

    return adj, nodes




components = []

ans = 0
icomp = 0

unconnected = {}

for s in speeds:
    newcomponents = []
    edges = speeds[s]

    adj, nodes = gendict(edges)

    # uudet kaaret komponentteihin
    visited = set()

    for nod in nodes:
        comp = set()
        dfs(nod)

        if len(comp) != 0:
            newcomponents.append((comp, s))

            for node in comp:
                complist[node] = icomp

            icomp += 1


    # saman nopeuden komponenttien parit, n choose k
    for c in newcomponents:
        ans += s * (fc(len(c[0])) // (fc(2) * fc(len(c[0]) - 2)))




    #
    components += newcomponents


def findconnected(start, cur, minspeed, notvisited):
    global ans
    minspeed = min(minspeed, cur[1])
    notvisited.remove(cur)

    # if len(cur[0] & start[0]) == 1:
    #     ans += minspeed * (len(start[0]) - 1) * (len(cur[0]) - 1)
    ans += minspeed * (len(start[0]) - 1) * (len(cur[0]) - 1)

    # notvisited = [(comp, speed)]
    for comp in notvisited:
        if len(cur[0] & comp[0]) == 1:
            if str(comp) not in cvisited:
                findconnected(start, comp, minspeed, notvisited)

    return


cvisited = set()


for c in components:
    oldcomp = deepcopy(components)

    findconnected(c, c, 99999999999, components)
    cvisited.add(str(c))

    components = oldcomp



print(ans)

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED