자동차 공장

• 오일러 경로 테크닉이 추가된 구간 쿼리 문제.
• 오일러 경로 테크닉을 적용해서 트리를 리스트로 변환해주기만 하면, 단순히 구간 업데이트 + 포인트 쿼리 문제가 된다. 이는 인접합 값의 차이로 구성된 배열을 만들어서 포인트 업데이트 + 구간 쿼리로 변환한 뒤, 펜윅 트리를 이용해서 해결이 가능하다.
• 전처리에는 오일러 경로 테크닉을 적용하는 데에 O(n), 펜윅 트리를 만드는데에 O(n), 모두 O(n)이 걸린다. 각각의 쿼리를 처리 하는 것은 O(logn)이 걸리므로 m개의 쿼리는 모두 O(mlogn)에 처리 가능하다. 따라서 총 시간 복잡도는 O(n+mlogn)
• 실수하기 쉬운 포인트는, p a x 쿼리에서, a의 월급은 변하지 않는다. 즉, a를 루트로 하는 서브트리 전체를 업데이트 하는 것이 아니라, 서브트리에서 a를 제외한 나머지만 업데이트 해줘야 한다. a를 루트로 하는 서브트리를 오일러 경로 테크닉으로 구간으로 변환했을때, a는 구간의 맨 앞에 오게 되므로, a를 제외한 구간을 구하려면 구간의 시작 위치에 +1을 해주기만 하면 된다.
  • 한가지 더 주의할 점은, p a x 쿼리는 a가 아무 부하가 없을 경우에도 들어올 수 있다. 이 경우에 인덱스에러가 나지 않도록 처리해줄 필요가 있다.

"""Solution code for "BOJ 2820. 자동차 공장".

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

import sys
from teflib import fenwicktree
from teflib import tgraph


def euler_tour_techinique(tree, root):
    subtree_ranges = [[None, None] for _ in tree]
    order = 0
    for node in tgraph.dfs(tree, root, yields_on_leave=True):
        if subtree_ranges[node][0] is None:
            subtree_ranges[node][0] = order
            order += 1
        else:
            subtree_ranges[node][1] = order
    return subtree_ranges


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    tree = [[] for _ in range(N)]
    salaries = [int(sys.stdin.readline())]
    for i in range(1, N):
        salary, boss = [int(x) for x in sys.stdin.readline().split()]
        salaries.append(salary)
        tree[boss - 1].append(i)

    subtree_ranges = euler_tour_techinique(tree, 0)
    fenwick = fenwicktree.FenwickTree(N + 1)
    for i in range(M):
        query = sys.stdin.readline().split()
        if query[0] == 'p':
            a, x = int(query[1]), int(query[2])
            beg, end = subtree_ranges[a - 1]
            beg += 1
            if beg < end:
                fenwick.update(beg, x)
                fenwick.update(end, -x)
        else:
            a = int(query[1])
            pos = subtree_ranges[a - 1][0]
            print(fenwick.query(0, pos + 1) + salaries[a - 1])


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree, teflib.tgraph.dfs