BOJ 11812 : K진 트리
2021. 5. 11. 01:20ㆍPS/Tree
11812번: K진 트리
첫째 줄에 N (1 ≤ N ≤ 1015)과 K (1 ≤ K ≤ 1 000), 그리고 거리를 구해야 하는 노드 쌍의 개수 Q (1 ≤ Q ≤ 100 000)가 주어진다. 다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. (1 ≤ x, y
www.acmicpc.net
트리에서 두 정점간의 거리를 구할때 할 수 있는 방법은
LCA(A,B) = A와 B의 최소 공통 조상
dist(A,B) = A와 B 사이 거리
이라고 할때,
dist(A,B) = dist(A, LCA(A,B))+ dist(LCA(A,B), B)
이다.
그러므로 우리는 LCA를 구해 두 정점 간의 거리를 알아내야 하는데, 방법은 나이브로 뚫린다.
K진 트리에서 현재 있는 노드 번호를 x라고 할때
자신의 부모 노드의 식은 (x+K-2)/K임을 이용해서 LCA를 구해준다.