BOJ 20535 - 최소 공통 조상과 쿼리
트리 압축(Virtual Tree)를 공부해보았다.
트리압축이란 트리에서의 어떠한 쿼리들에서 관심있는 노드의 개수의 모든 쿼리에서의 합이 작을 때, 관심있는 정점들만 뽑아서 작은 시간복잡도에 쿼리를 수행하게 해주는 테크닉이다.
현재 관심있는 노드들을 DFS 방문순서대로 정렬하고 인접한 것들의 LCA까지 해서 관심있는 정점을 뽑아주면
거기안의 정점들로 트리를 재구성할 수 있다.
자세한 내용은 튜토리얼 을 참고하자.
Comments