백준 11437 LCA

문제링크

https://www.acmicpc.net/problem/11437

문제

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> tree[50001];
int depth[50001];
int parent[20][50001];



void dfs(int node, int p) {
	parent[0][node] = p;
	depth[node] = depth[p] + 1;
	for (auto nxt : tree[node]) {
		if (nxt != p) {
			dfs(nxt, node);
		}
	}
	return;
}

int find_lca(int a, int b) {
	int da = depth[a];
	int db = depth[b];
	if (da < db) {
		swap(a, b);
	}
	da = depth[a];
	db = depth[b];
	int dif = da - db;
	for (int i = 19; i > -1; i--) {
		if (dif & (1 << i)) {
			a = parent[i][a];
		}
	}

	int LCA = a;
	if (a != b) {
		for (int i = 19; i > -1; i--) {
			if (parent[i][a] != -1 && parent[i][a] != parent[i][b]) {
				a = parent[i][a];
				b = parent[i][b];
			}
		}
		LCA = parent[0][a];
	}
	return LCA;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for (int i = 0; i < n-1; i++) {
		int a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	fill(&parent[0][0], &parent[19][50001], -1);
	dfs(1, 0);
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n; j++) {
			parent[i][j] = parent[i - 1][parent[i - 1][j]];
		}
	}



	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cout <<find_lca(a,b)<<'\n';	
	}
}

후기

LCA알고리즘은 처음 접해봐서 공부하며 풀었다.

https://seongjuk.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11437%EB%B2%88-LCA

https://www.crocus.co.kr/660#recentComments
해당 블로그에 정리가 잘 되어있다 !

쉽게 보고 접근했는데 생각보다 까다로웠다.
시간 될 때 한번 더 복습하자.