[백준11438 ]LCA2

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

vector<int>g[100001];
int depth[100001];
int dp[100001][30];
int visit[100001];
int n;
void dfs(int v,int d) //깊이 구하기 
{
	visit[v] = 1;
	depth[v] = d;
	for (int i = 0; i < g[v].size(); i++)
	{
		int data = g[v][i];
		if (!visit[data])
		{
			dp[data][0] = v;
			dfs(data, d + 1);
		}
	}
}
void MAKE() //각 노드의 조상 2k 구하기
{
	for (int j = 1; j < 30; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	 }
}
int lca(int u, int v)
{
	if (depth[u] < depth[v])swap(u, v);
	int diff = depth[u] - depth[v];
	for (int i = 0; diff; i++)
	{
		if (diff & 1) u = dp[u][i];
		
		diff >>= 1;
	}
	if (u == v)return u;

	//아니라면
	for(int i=29;i>=0;i--)
	{
		if (dp[u][i] != dp[v][i])
		{
			u = dp[u][i];
			v = dp[v][i];
		}
	}
	return dp[u][0];
}
int main()
{
	int a, b;
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 0);//깊이구하기
	MAKE();
	int m;
	cin >> m;
	while (m--)
	{
		scanf("%d %d", &a, &b);
		printf("%d\n", lca(a, b)); 
	}
}