Tree

• 아이디어보다는 사전지식의 결합으로 이루어진 문제.
• 트리에서 두 노드간의 거리를 구하는 쿼리는 LCA를 이용해서 처리할수 있다. {u의 depth} + {v의 depth} - {lca(u,v)의 depth}*2 로 구할 수 있다. 여기에서 어떤 노드 u를 지우는 것은 u의 서브트리 안에 모든 노드에 대해서 depth를 1 줄여주는 것과 동일한 효과를 낸다. lca를 구하는 것은 동일하고, u,v,lca(u,v)의 depth를 계산할때 원래 그 노드의 depth에서 줄어든 값들을 빼서 계산하면 된다.
• 서브트리 안에 모든 노드에 대해서 값을 업데이트 하는것은, 오일러경로 테크닉으로 트리를 배열로 변환한 뒤에, 펜윅트리나 세그먼트 트리를 사용해서 업데이트하면 된다. 레인지 업데이트 포인트 쿼리의 형태이므로, 포인트 업데이트 레인지 쿼리로 변환해서 처리할수 있고, 그러면 레이지 세그먼트 트리를 굳이 이용하지 않아도 된다.
• 전처리에는 LCA O(nlogn), 오일러경로테크닉 O(n), 펜윅트리 O(n) 이 걸리고, 쿼리마다 LCA O(logn), 펜윅트리 O(logn)이 걸린다. 총 시간복잡도는 O(nlogn + qlogn).
• 미리 만들어놓은 라이브러리를 사용하다보니, 오일러경로 테크닉과 LCA 전처리 부분에서 중복 사용되는 루틴이 있다. 라이브러리에서는 LCA를 HLD 기반으로 구현했는데, 그러다보니 LCA를 구하는 과정에서 이미 각 노드별 dfs방문 순서와 서브트리 사이즈가 계산되지만, 오일러경로 테크닉을 처리하는 과정에서 이것을 또다시 계산하게 된다. 이부분을 최적화하면 좀더 빨라질수도 있긴 하겠지만, 굳이 거기까지는 하지 않았다.

"""Solution code for "BOJ 13038. Tree".

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

Tags: [lca] [segment tree]
"""

import sys
from teflib import tree as ttree
from teflib import fenwicktree


def main():
    n = int(sys.stdin.readline())
    p = [int(x) - 1 for x in sys.stdin.readline().split()]

    tree = [[] for _ in range(n)]
    for u, p in enumerate(p, start=1):
        tree[u].append(p)
        tree[p].append(u)
    fenwick = fenwicktree.FenwickTreeForRangeUpdatePointQuery(n)
    lca = ttree.LowestCommonAncestor(tree)
    subtree_ranges = ttree.euler_tour_technique(tree)

    q = int(sys.stdin.readline())
    for _ in range(q):
        match sys.stdin.readline().split():
            case ['1', a, b]:
                u, v = int(a) - 1, int(b) - 1
                l = lca.lca_node(u, v)
                depth_u = lca.depth(u) - fenwick.get(subtree_ranges[u][0])
                depth_v = lca.depth(v) - fenwick.get(subtree_ranges[v][0])
                depth_l = lca.depth(l) - fenwick.get(subtree_ranges[l][0])
                dist = depth_u + depth_v - depth_l - depth_l
                print(dist)
            case ['2', v]:
                node = int(v) - 1
                beg, end = subtree_ranges[node]
                fenwick.range_update(beg, end, 1)


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.tree.LowestCommonAncestor
  • teflib.tree.euler_tour_technique
  • teflib.fenwicktree.FenwickTreeForRangeUpdatePointQuery