개발자 톡

연습문제 톡 [21년 재직자 대회 본선] 거리 합 구하기

거리합구하기 테스트 케이스

등록일
2022-10-21 14:35:57
조회수
559
작성자
qkd1101

# DFS

def dfs1(current, parent):
    subtreeSize[current] = 1
    for i in range(len(node[current])):
        child = node[current][i][0]
        weight = node[current][i][1]
        if child != parent:
            dfs1(child, current)
            distSum[current] += distSum[child] + subtreeSize[child]*weight
            subtreeSize[current] += subtreeSize[child]
    return


def dfs2(current, parent):
    for i in range(len(node[current])):
        child = node[current][i][0]
        weight = node[current][i][1]
        if child != parent:
            distSum[child] = distSum[current] + weight*(n-2*subtreeSize[child])
            dfs2(child, current)
    return

n = int(input())
node = [[] for _ in range(n+1)]
subtreeSize = [0]*(n+1)
distSum = [0]*(n+1)

for i in range(n-1):
    x, y, t = map(int, input().split())
    node[x].append([y,t])
    node[y].append([x,t])
    
dfs1(1,1)
dfs2(1,1)

for i in range(1, n+1):
    print(distSum[i])


이건 답보고 썼는데


5개 정도 테스트 케이스가 런타임 에러가 납니다


어떤 부분이 잘못되었을가요?


#[21년_재직자_대회_본선]_거리_합_구하기
#거리합구하기
#21년재직자대회본선

이 카테고리의 톡 더보기