최소 공통 조상(Lowest Common Ancestor / LCA)

1. 개념

트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A와 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점이다.

트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A 혹은 A의 조상이면서 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다.

2. 구현

보통 parent[i] 처럼 일차원 배열로 표현하던 부모 배열을 parent[u][k] 2차원 배열로 만든다. 이것이 뜻하는 바는 정점 u의 2^k 번째 부모라는 뜻이다.

이것을 풀어쓰면 2^(k+1) = 2^k + 2^k 이므로 , parent[u][k+1] = parent[parent[u][k]][k] 의 점화식을 구할 수 있다.

이 점화식에서  수 있듯이 k=i 일 때의 정보로 k=i+1 의 얻을 수 있고, DP를 사용해 알고리즘을 구성한다.

두 정점 u,v 에서 depth[u] >= depth[v] 일 때, 다음 두 과정을 반복한다.

    1) depth[u] > depth[v]일 때 u = parent[u]로 대체한다.

    2) u != v 일 때 u = parent[u] , v = parent[v] 로 대체한다.

하지만 1)에서 깊이 차이가 많이 날 때 부모를 하나씩 따라 올라가는 것은 비효율적이다.

깊이 차이를 이진수로 바꾸어서 대략적으로 올라가야할 높이를 가늠한다.

예를 들어 깊이 차이가 11일 때에는 1011(2) 이므로 2^3번째 부모로 가면되므로 더 효율적으로 알고리즘을 변경할 수 있다.

2)에서도 k를 큰 값부터 시도하면서 parent[u][k] != parent[v][k]이면 u,v를 함께 2^k만큼 부모 탐색을 한다.

*출처 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220820773477