38 lines
793 B
Python
38 lines
793 B
Python
import sys
|
|
from collections import deque
|
|
input = sys.stdin.readline
|
|
INF = float("inf")
|
|
|
|
N = int(input())
|
|
|
|
indegree = [0]*(N+1)
|
|
build_info = [[0] for _ in range(N+1)]
|
|
|
|
for i in range(1,N+1) :
|
|
line = list(map(int, input().split()))
|
|
build_info[i][0] = line[0]
|
|
for n in line[1:] :
|
|
if n == -1 :
|
|
break
|
|
build_info[n].append(i)
|
|
indegree[i] += 1
|
|
|
|
dp = [0]*(N+1)
|
|
qu = deque()
|
|
|
|
for i in range(1,N+1) :
|
|
if indegree[i] == 0 :
|
|
qu.append(i)
|
|
dp[i] = build_info[i][0]
|
|
|
|
while qu :
|
|
now = qu.popleft()
|
|
|
|
for nxt in build_info[now][1:] :
|
|
indegree[nxt] -= 1
|
|
dp[nxt] = max(dp[nxt], dp[now] + build_info[nxt][0])
|
|
|
|
if indegree[nxt] == 0 :
|
|
qu.append(nxt)
|
|
|
|
print("\n".join(list(map(str, dp[1:])))) |