<백준> 11438

LCA 2

문제
N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

이건 최소 공통 조상 빠르게 구하는 것으로 2의 k승씩 올라가서 비교하는 방식으로 푸는 것이다.

int n, m;
vector<vector<int>> tree;
int parent[21][100001];
vector<int>depth;
vector<bool> visited;
int kmax;

void DFS(int node, int level)
{
	visited[node] = true;
	depth[node] = level;

	for (int next : tree[node])
	{
		if (!visited[next])
		{
			parent[0][next] = node;
			DFS(next, level + 1);
		}
	}
}

int executeLCA(int a, int b)
{
	if (depth[a] < depth[b])
	{
		int temp = a;
		a = b;
		b = temp;
	}
	for (int k = kmax; k >= 0; k--)
	{
		if (pow(2, k) <= depth[a] - depth[b])
		{
			if (depth[b] <= depth[parent[k][a]])
				a = parent[k][a];
		}
	}
	for (int k = kmax; k >= 0 && a != b; k--)
	{
		if (parent[k][a] != parent[k][b])
		{
			a = parent[k][a];
			b = parent[k][b];
		}
	}
	int LCA = a;
	if (a != b)
		LCA = parent[0][LCA];
	return LCA;
}

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

	cin >> n;

	tree.resize(n + 1);

	for (int i = 0; i < n - 1; i++)
	{
		int s, e;
		cin >> s >> e;

		tree[s].push_back(e);
		tree[e].push_back(s);
	}

	depth.resize(n + 1);
	visited.resize(n + 1);
	int temp = 1;
	kmax = 0;
	
	while (temp <= n)
	{
		temp <<= 1;
		kmax++;
	}

	DFS(1, 0);

	for (int k = 1; k <= kmax; k++)
	{
		for (int p = 1; p <= n; p++)
		{
			parent[k][p] = parent[k - 1][parent[k-1][p]];
		}
	}
	
	cin >> m;

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