[노트] 최소공통조상(LCA) 찾기

문제: www.acmicpc.net/problem/11438

알고리즘을 나름 오랫동안 공부해왔던 나도 그래프와 트리 관련 문제는 많이 풀어보지 못한 것 같아, 요즘 가끔 생각날 때마다 관련 알고리즘들을 찾아보고 있다. 최근에는 LCA를 찾는 효율적인 알고리즘을 찾아보았는데, 경로에 대한 정보 없이 간단히 LCA만 딱 찾아내고 싶을 때는 복잡한 알고리즘이나 자료구조 없이 아주아주 간단한 테크닉으로도 가능하다는 것을 알게 되어 짧게 적어본다.

 

다음 사실을 관찰하는 순간 게임이 끝난다.

관찰: 노드 a와 b의 LCA는 a와 b 사이를 Euler tour로 방문하는 동안 지나친 노드들 중 가장 상위에 있는 노드이다.

(솔직 고백을 하자면, Euler tour of tree라는 개념도 이걸 배우면서 처음 알게 되었다)

 

어쨌든, 각 노드들을 Euler tour로 방문하는 경로와 그 노드의 레벨을 일렬로 쭉 적어 놓는 순간, 최솟값을 찾는 구간 쿼리 문제랑 똑같이 된다. 구간 쿼리는 sparse table을 사용하면 쿼리당 무려 \(O(1)\)에 처리가 가능하다.

 

트리에서 LCA만 딱 찾고 끝내는 경우는 매우 드물긴 하지만, 이 트릭을 조금만 응용하면 다른 트리 경로 쿼리 문제들도 해결할 수 있을 듯하다.

이 문제라든지, 이 문제라든지...

또 Euler tour를 찾고 sparse table을 만드는 과정에서 전처리 시간 \(O(N\log N)\)이 소요되므로, 수시로 변하는 트리에서는 사용할 수 없다. 이런 경우에는 HLD을 쓰거나, link-cut tree라는 걸 써야 한다나...