사용자 도구

사이트 도구


ps:problems:boj:13309

트리

ps
링크https://www.acmicpc.net/problem/13309
출처BOJ
문제 번호13309
문제명트리
레벨플래티넘 1
분류

동적 연결성

시간복잡도O(n+qlogn)
인풋사이즈n<=200,000, q<=200,000
사용한 언어Python
제출기록108420KB / 3216ms
최고기록3216ms
해결날짜2021/05/24

풀이

  • 트리에서의 동적 연결성 문제이다. 엣지를 삭제하는 쿼리만 주어지고, 오프라인 쿼리로는 해결할 수 없는 문제이다.
  • 트리에서의 동적 연결성에서 설명했듯이 여러가지 풀이가 가능하다. 자세한 내용은 링크 참조
  • 각 풀이를 구현해서 적용한 결과, 걸린 시간은 다음과 같았다.
    • [코드 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)으로 가장 빠르고, 실제 수행시간도 가장 빨랐다.

코드

코드 1

"""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()

코드 2

"""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()

코드 3

"""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()

토론

댓글을 입력하세요:
C J X I A
 
ps/problems/boj/13309.txt · 마지막으로 수정됨: 2021/05/24 14:54 저자 teferi