Escrito por Leonardo Paes
Conhecimento prévio necessário:
No enunciado do problema é dito que há somente um caminho entre quaisquer dois vértices. Teoricamente, grafos desse tipo são chamados de árvores. De modo prático, podemos usar deste fato para utilizarmos uma $$DFS$$ pouco modificada para solucionarmos nosso problema. Além do padrão, podemos utilizar como parâmetro para a função $$DFS$$ uma variável que guarde a distância percorrida para chegar no vértice atual $$v$$, partindo de certa raiz $$u$$, que basicamente nos diz a distância de $$u$$ pra $$v$$, justamente por só haver um caminho entre $$u$$ e $$v$$. Portanto, se utilizarmos o vértice $$A$$ do enunciado como a raiz da nossa $$DFS$$, saberemos a distância de $$A$$ pra $$B$$ assim que visitarmos o vértice $$B$$ na $$DFS$$.
Complexidade padrão da $$DFS$$ em uma árvore: $$O(N)$$. Confira o código abaixo para melhor entendimento: