영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.
모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.
직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,
첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)
둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.
다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)
사장은 상사가 없으므로 칭찬을 받지 않는다.
1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.
시간 초과
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
n, m = map(int, input().split())
graph1 = list(map(int, input().split()))
# 부하 배열
graph2 = [[] for i in range(n)]
a = []
dp = [0] * n
def DFS(node, score):
k = graph2[node - 1]
if k:
for i in range(len(k)):
dp[k[i] - 1] += score
DFS(k[i], score)
for i in range(1, len(graph1)):
graph2[graph1[i] - 1].append(i + 1)
for i in range(m):
x, y = map(int, input().split())
a.append([x, y])
for i in range(len(a)):
node = a[i][0] # 시작 노드
score = a[i][1]
dp[node - 1] += score
DFS(node, score)
print(*dp)
import sys
sys.setrecursionlimit(1000000)
def nextStep(transmission, nextTaker): # transmission: 전달되는 칭찬, nextTaker: 전달받을 직원
transmission += praise[nextTaker]
# 현재 nextTaker가 전달받은 칭찬 + 현재 nextTaker가 자신의 부하전달해줄 칭찬 누적
# => 다음 부하직원에게 넘길 준비
praise[nextTaker] += (transmission - praise[nextTaker])
# 현재 nextTaker가 직속 상사로부터 받은 칭찬을 누적
for i in sub[nextTaker]:
nextStep(transmission, i)
input = sys.stdin.readline
n, m = map(int, input().split())
boss = list(map(int, input().split()))
sub = [[] for i in range(n)]
praise = [0 for i in range(n)]
for i in range(n):
boss[i] -= 1
# 부하직원 배열인 sub를 편하게 만들기 위한 작업
for j in range(m):
i, w = map(int,input().split())
praise[i - 1] += w
for i in range(n):
if boss[i] != -2:
sub[boss[i]].append(i)
nextStep(0,0)
for i in praise:
print(i)