Chamemos as folhas iniciais de $$A$$ e $$B$$. Para sabermos em que folha as lagartas se encontram, é necessário que primeiro encontremos o lca de $$A$$ e $$B$$. Temos que $$tam_1$$ é a distância entre a folha $$A$$ e o $$lca(A, B)$$, e que $$tam_2$$ é a distância entre a folha $$B$$ e o $$lca(A, B)$$. Logo, a distância total entre as lagartas é $$dist = (tam_1+tam_2)$$, e a distância que cada uma das lagartas deverá percorrer é $$k = \frac{dist}{2}$$. Depois de calcularmos essa distância, subimos na árvore o vértice que possui $$tam \leq k$$ por $$k$$ níveis (utilizamos a matriz do lca para isso). Chamaremos esse vértice de $$r$$. Caso dist seja par, significa que as lagartas se encontrarão num mesmo vértice, o vértice $$r$$. Caso contrário, significa que as lagartas se encontrarão em vértices vizinhos, sendo esses $$r$$ e o pai de $$r$$.
Código para melhor entendimento:
| #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 |
Comente