트리

• 트리에서의 동적 연결성 문제이다. 엣지를 삭제하는 쿼리만 주어지는 유형으로, 트리 문제와 제목도 같고 내용도 거의 비슷하지만, 오프라인 쿼리로 처리하는것이 가능하기 때문에 훨씬 쉽다.
• 쿼리를 모두 읽어들인 뒤에 역순으로 처리하면, 실제 엣지를 삭제하는 쿼리를 엣지를 추가하는 쿼리로 처리할 수 있다. 이것은 Disjoint Set으로 쉽게 처리 가능. 연결성 체크과 엣지 추가가 각각 disjoint set의 find와 union으로 처리되므로 시간복잡도는 쿼리당 O(α(n)). 총 n+q개의 쿼리를 처리하는 데에 O((n+q)*α(n))의 시간복잡도가 된다.
• 이렇게 오프라인 쿼리 방식으로 풀었을때는 약 1400ms만에 통과되었지만 (다른사람의 가장 빠른 답안은 약 1100ms), 궁금해서 온라인으로 처리하는 가장 빠른 방법인 서브트리 쿼리 + 펜윅트리 방식으로도 풀었을때는 약 4100ms가 걸렸다.

"""Solution code for "BOJ 13306. 트리".

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

import sys
from teflib import disjointset


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    parents = [None] + [int(sys.stdin.readline()) for _ in range(N - 1)]
    queries = [sys.stdin.readline().split() for _ in range(N - 1 + Q)]

    dsu = disjointset.DisjointSet(N)
    answers = []
    for query in reversed(queries):
        if query[0] == '0':
            b = int(query[1])
            dsu.union(b - 1, parents[b - 1] - 1)
        else:
            c, d = int(query[1]), int(query[2])
            answers.append(dsu.find(c - 1) == dsu.find(d - 1))

    print('\n'.join('YES' if x else 'NO' for x in reversed(answers)))


if __name__ == '__main__':
    main()

• Dependency: teflib.disjointset.DisjointSet