https://www.acmicpc.net/problem/14268
처음에는 칭찬을 받을때마다 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)#출력
'백준 파이썬 코딩' 카테고리의 다른 글
백준 25919 Lost Edge 파이썬 (1) | 2022.11.07 |
---|---|
백준 1026 보물 파이썬 (0) | 2022.11.06 |
백준 18290 NM과 K (1) 파이썬 (0) | 2022.10.31 |
백준 2822 점수 계산 파이썬 (0) | 2022.10.27 |
백준 20115 에너지 드링크 파이썬 (0) | 2022.10.27 |