noics5avp2.cpp

#include <bits/stdc++.h>
#define pb push_back
#define MAXN 5010
using namespace std;

int n, lca[MAXN][25], nivel[MAXN];
vector < vector < int > > grafo;

inline void dfs(int u, int pai)
{
	lca[u][0] = pai;
	nivel[u] = nivel[pai]+1;
	for(int i = 1 ; i <= 20 ; i++)
	{
		if(lca[u][i-1] != -1) lca[u][i] = lca[lca[u][i-1]][i-1];
	}
	for(int i = 0 ; i < grafo[u].size() ; i++)
	{
		int v = grafo[u][i];
		if(v != pai) dfs(v, u);
	}
}

inline int funclca(int a, int b) //funcao que calcula o lca
{
	if(nivel[b] > nivel[a]) swap(a, b);
	for(int i = 20 ; i >= 0 ; i--)
	{
		if(nivel[a] - (1 << i) >= nivel[b]) a = lca[a][i];
	}
	if(a == b) return a;
	for(int i = 20 ; i >= 0 ; i--)
	{
		if((1 << i) < nivel[a] and (1 << i) < nivel[b] and lca[a][i] != lca[b][i])
		{
			a = lca[a][i];
			b = lca[b][i];
		}
	}
	return lca[a][0];
}

inline int funcvert(int a, int niv) //funcao que sobe o vertice
{
	for(int i = 20 ; i >= 0 ; i--)
	{
		if(nivel[a] - (1 << i) >= niv) a = lca[a][i];
	}
	return a;
}

int main()
{
	cin >> n;
	grafo.resize(n+3);
	memset(lca, -1, sizeof lca); //coloco todas as posições do lca como -1
	for(int i = 0 ; i < n-1 ; i++)
	{
		int a, b;
		cin >> a >> b;
		grafo[a].pb(b); 
		grafo[b].pb(a); 
	}
	nivel[0] = 0; 
	dfs(1, 0); // chamo a dfs que calcula-rá a matriz do lca e o nivel de cada um
	int l;
	cin >> l;
	while(l--)
	{
		int a, b;
		cin >> a >> b;
		int r = funclca(a, b); //calculo o lca de a e b
		int tam1 = nivel[a] - nivel[r], tam2 = nivel[b] - nivel[r]; //calculo a distancia das duas folhas ao lca
		int resp = (tam1+tam2)/2; // distancia que cada um precisa percorrer até se encontrarem
		
		if(nivel[a] > nivel[b]) r = funcvert(a, nivel[a] - resp); //verifico qual está mais distante do lca, subo ele
		else r = funcvert(b, nivel[b] - resp);                    //até o resp-ésimo vertice
		
		if((tam1+tam2)%2 == 0) cout << "As lagartas se encontram em " << r << ".\n"; //se a distancia for par, o vertice que elas se
		else																		// é o r
		{
			int k1 = r, k2 = lca[k1][0]; //caso contrario, os vertices são o r e o pai de r
			if(k2 < k1) swap(k1, k2);
			cout << "As lagartas pularam para sempre a partir de " << k1 <<  " e " << k2 << ".\n";
		}
	}
} //10938uva