백준 소스코드 [C++] 11438 LCA 2

www.acmicpc.net/problem/11438

11438번: LCA 2

백준 소스코드 [C++] 11438 LCA 2

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int n, m;
vector<int> tree[100000];
int parent[100000][21];
int level[100000];
int chk[100000];

void getParentandLevel(int Parent) {
	chk[Parent] = true;
	for(auto son: tree[Parent])
		if (chk[son] == false) {
			parent[son][0] = Parent;
			level[son] = level[Parent] + 1;
			getParentandLevel(son);
		}
	return;
}

void getGrand() {
	for(int ith=1;ith<=20;ith++)
		for (int son = 0;son < n;son++) 
			if (parent[son][ith] == 0)
				parent[son][ith] = parent[parent[son][ith-1]][ith-1];
	return;
}

void searchAnc(int y, int x) {
	if (level[y] < level[x]) swap(y, x);

	for (int i = 20;0 <= i;i--)
		if (level[y] - level[x] >= (1<<i)) y=parent[y][i];

	if (y == x) cout << y + 1<<'\n';
	else {
		for (int i = 20;0 <= i;i--)
			if (parent[y][i] != parent[x][i]) {
				y = parent[y][i];
				x = parent[x][i];
			}
		cout << parent[y][0]+1<< '\n';
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int u, v;
	cin >> n;
	for(int i=0;i<n-1;i++) {
		cin >> u >> v;
		tree[u - 1].push_back(v - 1);
		tree[v - 1].push_back(u - 1);
	}
	getParentandLevel(0);
	getGrand();

	cin >> m;
	while (m--) {
		cin >> u >> v;
		searchAnc(--u, --v);
	}
	return 0;
}