Chamemos as folhas iniciais de 
e 
. Para sabermos em que folha as lagartas se encontram, é necessário que primeiro encontremos o lca de e . Temos que 
é a distância entre a folha e o 
, e que 
é a distância entre a folha e o . Logo, a distância total entre as lagartas é 
, e a distância que cada uma das lagartas deverá percorrer é 
. Depois de calcularmos essa distância, subimos na árvore o vértice que possui 
por 
níveis (utilizamos a matriz do lca para isso). Chamaremos esse vértice de 
. Caso dist seja par, significa que as lagartas se encontrarão num mesmo vértice, o vértice . Caso contrário, significa que as lagartas se encontrarão em vértices vizinhos, sendo esses e o pai de .
Código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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 |