LCA란

Lowest Common Ancestor란 최소 공통 조상을 찾는 알고리즘이고 두 정점 u,v 에거 가장 가까운 공통 조상을 찾는 과정을 말한다.

---

1. 반복문을 이용한 LCA

if (d[a] > d[b]) {
	int tmp = a;
	a = b;
	b = tmp;
} //b의 높이가 더 크게 만들어줍니다.

while (d[a] != d[b]) {
	b = parent[b];
}//a와 b의 높이를 맞춰줍니다.

while (a != b) {
	a = parent[a];
	b = parent[b];
}//함께 부모로 올라가며 부모가 같으면 while문을 종료합니다.

위와 같은 방법은 구현은 쉽지만 시간 복잡도가 최악의 경우 O(N)의 시간 복잡도가 요구됩니다.
모든 쿼리를 처리할 때의 시간 복잡도는 O(NM)으로 시간효율적인 면에서 좋지않기 때문에 구현은 어렵지만 훨씬 빠르게 dp로 구현할 수 있습니다.

---

2. DP를 이용한 LCA

DP를 이용했을 때 시간 복잡도 : O(logN)
쿼리가 있을 경우 : O(MlogN)

oid dfs(int v, int d){
	visit[v] = 1;
	depth[v] = d;
	for(auto i : g[v]){
		if(!visit[i]){
			dp[i][0] = v;
			dfs(i, d+1);
		}
	}
}dfs를 이용하여 dp[i][0]에 부모를 저장합니다.

void make_table(){
	for(int j=1; j<30; j++){
		for(int i=1; i<=n; i++){
			dp[i][j] = dp[ dp[i][j-1] ][j-1];
		}
	}
}
//dp[i][j] = dp[ dp[i][j-1] ][j-1];
//8번째 조상은 = 4번째 조상 + 4번째 조상
//의 원리

for (int i = 99 ; i >= 0; i--) {
	if (d[b] - d[a] >= (1 << i)) {
		b = parent[b][i];
	}
} // 깊이 차이가 13일 경우
13<32 이므로 패스
13<16 이므로 패스
13>=8 이므로 8칸 이동
5>=4 이므로 4칸 이동
1>=1 이므로 1칸 이동
13 = 8+4+1

if(x==y) return x; // 부모가 같을 경우 반환
for (int i = 99; i >= 0; i--) {
	if (parent[a][i] != parent[b][i]) {
		a = parent[a][i];
		b = parent[b][i];
	}
}
// 부모가 다를 경우 조상을 향해 올라가며 같은지 비교합니다.
//