최소 공통 조상

이 문제는 시간복잡도가 O(N x M) 이면 통과되는 시간 제한이 있다

 

 

 

가장 가까운 조상은 공통된 조상 중에서 가장 낮은 조상이라고도 할 수 있다
그렇기에 영어권에서는 (Lowest : 가장 낮은) 라는 단어를 사용한다

 

 

 

 

 

 

 

 

 

 

 

N과 M의 범위가 최대 10만개라고 하면 시간 초과 판정을 받는다
이때는 어떻게 해결하는가?

 

 

 

 

 

거슬러 올라갈 때는 가능하면 빠르게 2의 제곱꼴로 올라가게 한다
예시로 거리가 3이면 1번째에 2칸 올라가고 2번째에 1칸 올라간다

 

 

 

 

 

 

lca 함수에서 먼저, 항상 b가 더 깊도록 swap을 진행한다

(1 << i) :  1 * (2의 i승)