[C++] 최소 공통 조상( lowest common ancestor, LCA ) 구하기

최소 공통 조상( lowest common ancestor )이란최소 공통 조상( LCS )은, 그래프에서 선택된 두 정점의 공통된 조상 정점 중에서, 가장 큰 깊이를 가진 정점을 말합니다.참고로, 노드의 깊이( depth )는 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 말합니다.  위의 그래프에서, 정점 6과 7의 공통 조상은 4, 2, 1번 정점들입니다.그중에서 깊이가 가장 큰 4번 정점이 최소 공통 조상입니다. 이 최소 공통 조상을 구하는 알고리즘은 두 단계로 나눠집니다.첫 번째, 두 정점의 깊이를 일치시킵니다.두 번째, 같은 깊이를 가진 두 정점의 트리 경로를 따라 동시에 위로 올라가면서, 처음으로 일치하는 부모를 찾습니다.이 부모가 LCA가 됩니다. 아래의 그래프에서 6번과 1..