LCA（模版）提解

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll g_llN = 0;
ll g_llM = 0;
ll g_llS = 0;
vector<ll> g_vecA[500005];
ll g_llDp[500005] = {0};
ll g_llF[500005][33] = {0};

void dfs(ll llU, ll llF)
{
	g_llF[llU][0] = llF;
	g_llDp[llU] = g_llDp[llF]+1;
	
	for (ll i = 0; i < g_vecA[llU].size(); i++)
	{
		if (llF != g_vecA[llU][i])
		{
			dfs(g_vecA[llU][i], llU);
		}
	}
}

void init()
{
	for (ll j = 1; (1 << j) <= g_llN; j++)
	{
		for (ll i = 1; i <= g_llN; i++)
		{
			g_llF[i][j] = g_llF[g_llF[i][j-1]][j-1];
		}
	}
}

ll LCA(ll llU, ll llV)
{
	if (g_llDp[llU] < g_llDp[llV])
	{
		swap(llU, llV);
	}
	
	for (ll i = 22; i >= 0; i--)
	{
		if (g_llDp[g_llF[llU][i]] >= g_llDp[llV])
		{
			llU = g_llF[llU][i];
		}
	}
	
	if (llU == llV)
	{
		return llU;
	}
	
	for (ll i = 22; i >= 0; i--)
	{
		if (g_llF[llU][i] != g_llF[llV][i])
		{
			llU = g_llF[llU][i]; 
			llV = g_llF[llV][i]; 
		}
	}
	
	return g_llF[llU][0];
}

int main()
{
	scanf("%lld%lld%lld", &g_llN, &g_llM, &g_llS);
	
	for (ll i = 1; i < g_llN; i++)
	{
		ll llX = 0;
		ll llY = 0;
		
		scanf("%lld%lld", &llX, &llY);
		
		g_vecA[llX].push_back(llY);
		g_vecA[llY].push_back(llX);
	}
	
	dfs(g_llS, 0);
	init();
	
	for (ll i = 1; i <= g_llM; i++)
	{
		ll llA = 0;
		ll llB = 0;
		
		scanf("%lld%lld", &llA, &llB);
		
		printf("%lld\n", LCA(llA, llB));
	}
	
	return 0;
}