최소 공통 조상 알고리즘 : LCA(Lowest Common Ancestor)

최소 공통 조상 알고리즘은 트리 구조에서 두 정점 a, b에서 가장 가까운 공통 조상을 찾는 알고리즘이다

위 트리에서 두 정점 (4, 7)의 LCA는 1이고, (12, 11)의 LCA는 8이다.

위 트리를 예로 들었을 때, DP를 통해 a와 b의 LCA를 구하는 방법은 다음과 같다.

1. 먼저 트리를 한번 순회하며 각 정점에 대한 깊이와 부모를 정해준다.

2. 계산된 depth의 최댓값을 가지고 각 정점에 대해 2^i 번째 조상을 저장하는 배열을 만든다.
   이때, 2^i 번째 조상을 찾아가는 식은 다음과 같다.
   parent[i][v] = parent[i-1][parent[i-1][v]]
   * 이 식을 말로 풀어보면 정점 v의 2^i 번째 부모는 정점 v의 2^(i-1) 번째 부모 노드의 2^(i-1) 번째 부모노드이다.

3. 두 정점의 깊이가 다르다면 위 배열을 사용해서 depth가 더 큰 정점의 depth를 낮춰준다.

if(depth[a] - depth[b] >= (1<<i)) {
    a = depth[i][a];
}

만약 depth를 맞추고 a와 b를 비교했을때 같다면 LCA이다.

4. depth는 같지만 a와 b가 다르다면, 각 정점의 2^i 조상들을 확인하면서 조상이 다르면 위로 올린다.

if(depth[i][a] != depth[i][b]) {
    a = depth[i][a];
    b = depth[i][b];
}

위 과정을 전부 마치고 나온 a나 b의 부모가 LCA이다.