회사 문화 1

• 회사 문화 2에서 했듯이 오일러 경로 테크닉을 적용한 뒤에, 구간 쿼리로 풀어도 되긴 한다. 이 경우는 구간합 업데이트가 미리 주어진 이후에 포인트 쿼리를 요구하는 문제가 되므로, 구간 합에서 설명한 원소의 값을 구간합으로 처리하는 테크닉을 적용해서, m개의 쿼리를 O(1)에 처리하고 O(n)으로 prefix sum을 만든 뒤, 각 노드의 값을 O(1)에 계산하는 것이 가능하다. 그렇게 하면 전체 복잡도는 O(n+m)
• 하지만, 저렇게까지 돌아갈 필요가 없다. 그냥 m개의 쿼리를 처리하며 각 노드들의 칭찬값을 바로 업데이트 해둔 뒤에, 트리를 루트에서부터 순회하면서 자식 노드의 칭찬값에 부모 노드의 칭찬값을 더해주는 것으로 충분하다. 그것만으로도 부모 노드의 칭찬값이 모든 자손들에게 전파되게 된다. 시간 복잡도는 똑같이 O(n+m)이지만 코드가 훨씬 간단해진다.

"""Solution code for "BOJ 14267. 회사 문화 1".

- Problem link: https://www.acmicpc.net/problem/14267
- Solution link: http://www.teferi.net/ps/problems/boj/14267
"""

import sys
from teflib import tgraph


def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    tree = [[] for _ in range(n)]
    bosses = [int(x) for x in sys.stdin.readline().split()]
    for employee, boss in enumerate(bosses):
        if boss != -1:
            tree[boss - 1].append(employee)    
    praises = [0] * n
    for _ in range(m):
        i, w = [int(x) for x in sys.stdin.readline().split()]
        praises[i - 1] += w
        
    stack = []
    for employee in tgraph.dfs(tree, 0, stack=stack):
        if employee != 0:
            boss = stack[-2]
            praises[employee] += praises[boss]            

    print(*praises)
    
    
if __name__ == '__main__':
    main()

• Dependency: teflib.tgrapg.dfs