백준 14268 회사 문화 1 파이썬

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

14268번: 회사 문화 2

 

처음에는 칭찬을 받을때마다 dp값을 갱신시켜줬었다. 하지만, 그렇게 했더니 시간초과가 났고 칭찬받은 칭찬의 크기를 저장해준뒤 부모노드를 저장한 배열을 자식노드를 저장한 배열로 바꿔준뒤 dp값이 0이 아니면 dfs를 돌려 re값을 채워줬다.

핵심 Key-word

1. 입력받을때마다 dp값을 갱신시켜주면 안 됨.

2. 부모노드를 저장한 배열을 자식노드를 저장한 배열로 바꿔줌.

3. dp가 0이 아닐때 dfs를 돌려 re 값을 채워줌.

4. 재귀 깊이를 늘려줌

 

import sys
input =sys.stdin.readline
sys.setrecursionlimit(10**5)#재귀 깊이 늘리기
def dfs(m,t):#dfs작업
    for i in maps[m]:
            re[i]+=t#결과값 갱신
            dfs(i,t)

def backend():#자식노드 저장배열 만드는 과정 
    for i in range(n-1,0,-1):
        maps[s[i]-1].append(i)


n,k = map(int,input().split())
s = list(map(int,input().split()))
maps = [[]for _ in range(n)]
dp = [0]*n
backend()
re = [0]*n
for _ in range(k):
    a,b = map(int,input().split())
    dp[a-1]+=b#칭찬의 크기를 더해줌
    re[a-1]+=b#칭찬을 받았으니 +해줌
#dfs(a-1,b)
for i in range(n):
    if dp[i]!=0:#칭찬의 크기가 0이 아니면
        dfs(i,dp[i])#dfs해줌
print(*re)#출력