백준 11437 LCA (C++)

11437번: LCA

트리를 이용한 문제이다. 공통되는 부모 노드를 찾기 위해 먼저 주어진 간선을 이용해 각 노드의 부모 노드와 깊이를 따로 저장해주었다. 그리고 공통 부모 노드를 찾기를 원하는 두 노드의 깊이를 비교해 두 노드의 깊이가 같아질때까지 더 깊은 노드의 레벨을 낮춰준다. 그리고 깊이가 같을 때 동시에 거슬러 올라가며 부모 노드를 찾아 이를 출력해주었다.
주어진 간선들을 통해 트리를 만드는 방법은 이전에 문제에서 활용해보아서 잘 알고 있었는데 공통 부모를 찾기 위해 깊이를 이용한다는 점은 이번 문제를 통해 처음 활용해보았다. 이러한 풀이 방식에 대해서도 잘 알아두어야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> nv[50001];
int parent[50001];
int level[50001];
vector<pair<int, int>> mv;

void createTree(int pnode, int node) {
	parent[node] = pnode;
	level[node] = level[pnode] + 1;

	for (int i = 0; i < nv[node].size(); i++) {
		int child = nv[node][i];

		if (pnode == child) continue;

		createTree(node, child);
	}
}

void lca(int a, int b) {
	if (level[a] < level[b]) swap(a, b);

	while (level[a] != level[b]) {
		a = parent[a];
	}

	while (a != b) {
		a = parent[a];
		b = parent[b];
	}

	cout << a << "\n";
}

void solution() {
	createTree(0, 1);

	for (int i = 0; i < mv.size(); i++) {
		int a = mv[i].first;
		int b = mv[i].second;

		lca(a, b);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

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

	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		mv.push_back({ a,b });
	}

	solution();
	
	return 0;
}