• 트리에서의 동적 연결성 문제이다. 엣지를 삭제하는 쿼리만 주어지고, 오프라인 쿼리로는 해결할 수 없는 문제이다.
• 트리에서의 동적 연결성에서 설명했듯이 여러가지 풀이가 가능하다. 자세한 내용은 링크 참조
• 각 풀이를 구현해서 적용한 결과, 걸린 시간은 다음과 같았다.
  • [코드 1] 경로 업데이트(HLD) + Fenwick tree : 5832ms
  • [코드 2] 서브트리 업데이트(Euler Tour Technique) + Lazy segment tree : 시간 초과. (PyPy로는 2536ms)
  • [코드 3] 서브트리 업데이트(Euler Tour Technique) + Xor Fenwick tree : 3364ms
  • [코드 생략] DFS로 업데이트 : 시간 초과 (PyPy로도 시간 초과)
• [코드 3] 방법이 시간 복잡도도 O(n+qlogn)으로 가장 빠르고, 실제 수행시간도 가장 빨랐다.

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

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

import sys
from teflib import fenwicktree
from teflib import ttree


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    tree = [[] for _ in range(N)]
    for i in range(1, N):
        a = int(sys.stdin.readline())
        tree[a - 1].append(i)
        tree[i].append(a - 1)
    hld = ttree.HeavyLightDecomposition(tree, root=0)
    fenwick = fenwicktree.FenwickTree(N)

    for i in range(Q):
        b, c, d = [int(x) for x in sys.stdin.readline().split()]
        ranges = hld.get_ranges_in_path(b - 1, c - 1, 
                                        should_include_top_node=False)
        is_connected = all(fenwick.query(*r) == 0 for r in ranges)
        print('YES' if is_connected else 'NO')
        if d == 0:
            continue
        u = (b - 1) if is_connected else (c - 1)
        fenwick.set(hld.get_pos(u), 1)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.fenwicktree.FenwickTree
  • teflib.ttree.HeavyLightDecomposition

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

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

import sys
from teflib import segmenttree
from teflib import ttree


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

    subtree_ranges = ttree.euler_tour_technique(tree, 0)
    segtree = segmenttree.LazySegmentTree(
        [0] * N,
        merge=lambda l, r: 0,
        update_value=lambda v, p, size: max(v, p),
        update_param=max)
    for i in range(Q):
        b, c, d = [int(x) for x in sys.stdin.readline().split()]
        b_pos = subtree_ranges[b - 1][0]
        c_pos = subtree_ranges[c - 1][0]
        is_connected = (segtree.get(b_pos) == segtree.get(c_pos))
        print('YES' if is_connected else 'NO')
        if d == 1:
            if is_connected:
                segtree.range_update(*subtree_ranges[b - 1], b_pos)
            else:
                segtree.range_update(*subtree_ranges[c - 1], c_pos)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.segmenttree.LazySegmentTree
  • teflib.ttree.euler_tour_techinique

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

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

import random
import sys
from teflib import fenwicktree
from teflib import ttree


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

    subtree_ranges = ttree.euler_tour_technique(tree, root=0)
    fenwick = fenwicktree.XorFenwickTree(N + 1)
    for i in range(Q):
        b, c, d = [int(x) for x in sys.stdin.readline().split()]
        b_group = fenwick.query(0, subtree_ranges[b - 1][0] + 1)
        c_group = fenwick.query(0, subtree_ranges[c - 1][0] + 1)
        is_connected = (b_group == c_group)
        print('YES' if is_connected else 'NO')
        if d == 1:
            update_val = random.getrandbits(32)
            if is_connected:
                fenwick.update(subtree_ranges[b - 1][0], update_val)
                fenwick.update(subtree_ranges[b - 1][1], update_val)
            else:
                fenwick.update(subtree_ranges[c - 1][0], update_val)
                fenwick.update(subtree_ranges[c - 1][1], update_val)


if __name__ == '__main__':
    main()

• Dependency
  • teflib.fenwicktree.XorFenwickTree
  • teflib.ttree.euler_tour_techinique