LCA(Lowest Common Ancestor)란, 트리 상에서 두 노드의 가장 가까운 공통 조상 노드를 의미합니다. 이를 구하는 방법으로는 여러가지가 있지만, 가장 일반적인 방법은 최소 공통 조상을 찾는 알고리즘 중 하나인 Tarjan's off-line algorithm을 이용하는 방법입니다. Tarjan's off-line algorithm은 DFS(Depth-First Search)를 이용하여 각 노드의 부모 노드와 깊이(depth)를 구하고, 두 노드의 깊이가 같아질 때까지 각 노드를 끌어 올리며 공통 조상을 찾는 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(N+Q)로, N은 노드의 개수, Q는 쿼리의 개수입니다. LCA using Tarjan's algorithm ( with Javasc..
