BOJ 11812 : K진 트리
BOJ 11812 : K진 트리 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진 트리에서 현재 있는 ..
2021.05.11