LCA 알고리즘이란? 트리에서 두 정점 $u$, $v$의 가장 가까운 조상을 찾는 알고리즘이다. 즉, 두 정점 $u$, $v$가 만날 때까지 루트 쪽으로 정점을 올려주면 두 정점이 만났을 때의 정점이 최소 공통 조상이 된다. 이 트리에서 $5$번 정점과 $7$번 정점의 최소 공통 조상은 $2$번이고, $4$번 정점과 $6$번 정점의 최소 공통 조상은 1번 정점이다. 최소 공통 조상을 구한다면 트리에서 두 정점 간의 최단 거리 등을 쉽게 구할 수 있고, 그 외에도 다양하게 사용할 수 있다. 이를 구하기 위해 DP를 이용해서 $O(logN)$으로 해결할 것이다. 구현 1. dfs를 통해 트리의 각 정점의 깊이와 정점들의 조상을 구한다. 이때 조상은 $2^{0}$, $2^{1}$, $2^{2}$, ...번째 ..
