https://www.youtube.com/watch?v=xLvL1C1LfnY&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=40

📌 최소공통조상(LCA)

트리 그래프에서 임의의 두 노드를 선택했을 떄 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음으로 공통으로 만나게되는 부모노드를 말함

◾ 최소공통조상 빠르게 구하기

• 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려주는 방식에서 2^k씩 올라가 비교하는 방식
  따라서 , 기존에 자신의 부모 노드만 저장해 놓던 방식에서 첫 번째 위치의 부모 노드까지 저장해둬야함

1. 부모 노드 저장 배열 만들기

• 부모 노드 배열의 정의

p[K][N] = N번 노드의 2^k번째 부모의 노드 번호 

• 부모 노드 배열의 점화식

p[K][N] = P[K-1][P[K-1][N]]

- 배열에서 K는 `트리 깊이 > 2^K`를 만족하는 최댓값 

→ N의 2³ 번째 부모는 N의 2² 번째 부모의 2² 번째 부모

• 초기화 된 배열을 바탕으로 K를 1씩 증가시키면서 나머지 배열을 채움

  2. 선택된 두 노드의 깊이 맞추기

• P배열을 이용해 기존 한 단계씩 맞췄던 깊이를 2^k 단위로 넘어가면서 맞춘다.

  3. 최소 공통 조상 찾기

• K값을 1씩 감소하면서 P 배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.

• 최초로 달라지는 K에 대한 두 노드의 부모 노드를 찾아 이동
  이를 K가 0이 될 때 까지 반복

• 반복문이 종료된 후 이동한 2개의 노드가 같은 노드라면 해당 노드가, 다른 노드라면 바로 위의 부모 노드가 최소 공통 조상이 됨.