BOJ 17101: Dynamic Centroid

Link

• https://www.acmicpc.net/problem/17101

Tag

• Sparse Table

• Segment Tree

• Euler Tour Technique

Time Complexity

• $O(NlgN)$

 N개의 정점으로 이루어진 트리가 주어지고, 1부터 N까지의 k에 대해, 1번 정점부터 k번 정점까지만 사용한 트리의 센트로이드를 출력해야 한다.

 정점이 하나 추가되면 센트로이드는 최대 1칸 이동한다. 그 방향은 정점이 새로 추가된 쪽일 것이다. 증명은 안해봤는데, 직관적이고 짜니까 맞더라. 1번 정점을 루트로 잡자. 새로 추가된 정점이 현재 센트로이드를 루트로 하는 서브트리 안에 있다면, 다음 센트로이드의 후보는 새로 추가된 정점에서 (거리-1) 만큼 위로 이동한 점일 것이다. 서브트리 안에 없다면, 다음 후보는 현재 센트로이드의 부모다.

 후보가 실제로 valid 한지는 서브트리의 크기를 보면 된다. 정점이 추가되면서 서브트리의 크기를 구해야 하므로 Euler Tour Technique에 세그를 스까서 잘 해주면 된다.

Code