이번 문제는 DFS를 통해 해결하였다. 처음에는 각 직원의 직속 부하만을 인접 리스트 형태로 저장하고, 칭찬 리스트를 순회하며 각 직원의 직속 부하에게 칭찬 점수를 전달하는 재귀함수를 작성하였다. 그러나 시간 초과가 발생하였고, 재귀 함수를 한번만 호출할 수 있는 방법에 대해 생각해보았다.

이 문제에서는 자신보다 직급이 높은 사람이 받은 칭찬을 모두 받게 되는 문제이다. 이를 이용하여 자신의 직속 상사를 나타내는 리스트를 하나 더 만들고, 칭찬 리스트의 값들을 해당 직원들에게만 적용하고, 1번 직원부터 재귀함수로 순회하며 자신의 직속상사의 점수를 자신의 점수에 더하도록 하였고, 이 방법을 사용하여 재귀함수 호출을 한번만 할 수 있었다.

Code

import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
tmp = list(map(int, input().split()))
relation = [[] for _ in range(n+1)]
superior = [0 for _ in range(n+1)]
answer = [0 for _ in range(n+1)]
for i in range(n):
    if tmp[i] == -1:
        continue
    relation[tmp[i]].append(i+1)
    superior[i+1] = tmp[i]
thank = []
for _ in range(m):
    r, v = map(int, input().split())
    answer[r] += v
def delivery(cur):
    answer[cur] += answer[superior[cur]]
    if relation[cur]:
        for nxt in relation[cur]:
            delivery(nxt)
delivery(1)
print(*answer[1:])