알고리즘 공부방

LCA란, Lowest Common Ancestor 로, 트리에서의 최소 공통 조상이다. 공통 조상은 두 노드에 대해, 두 노드 모두의 자손인 조상 노드들을 의미하며, 그중 깊이가 최대인 것, 즉 가장 아래쪽에 위치한 노드를 두 노드에 대한 최소 공통 조상 이라 한다. 기본적인 아이디어는 두 노드에 대해서 1. 두 노드의 깊이가 같도록 하나의 노드를 올려준 후, 2. 두 노드가 같아질 때까지 올려준다. 이 연산을 그냥 실행하면, 최악의 경우에 $O(N)$의 시간이 걸릴 수 있다. 이는 Sparse Table 을 사용하여 LCA 연산을 $O(logN)$에 처리할 수 있다. 가장 먼저 dfs 한번을 돌면서 각 노드들의 깊이와, 노드들의 부모를 sparse table 안에 저장한다. 다음, $par[i][j]..