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:
https://gist.github.com/lawrencefmm/e58532b8ec3d3decdac4b70b6b70eaee
Deixe um comentário