14267번 회사 문화 1

문제

https://www.acmicpc.net/problem/14267

접근 방식

처음에는 매 칭찬마다 dfs를 수행했는데 시간 초과가 났다. 최악의 경우, 트리 깊이는 n인데 칭찬 역시 m개 라면 100000 * 100000번의 dfs 재귀 호출이라 그런가보다.

다른 분들의 풀이를 참고해보니, 미리 칭찬의 시작점들을 dp 배열에 저장하면 루트(dp[0])부터 dfs를 한번 호출하는 걸로 끝낼 수 있었다. 왜 이생각을 못했지,,!!

코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


n, m = map(int, input().split())

tree = [list() for _ in range(n)]  # 상사-부하 관계
info = list(map(int, input().split()))
for i in range(1, n):
    tree[info[i] - 1].append(i)

dp = [0] * n  # 누적 칭찬


def dfs(cur):
    for nxt in tree[cur]:
        dp[nxt] += dp[cur]  # 직속 부하에게 칭찬 누적
        dfs(nxt)


for _ in range(m):
    p, w = map(int, input().split())
    dp[p - 1] += w

dfs(0)  # 시간 초과 수정 -> dfs 한번

print(*dp)