개발자 톡
연습문제 톡
[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년재직자대회본선