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 pouco modificada para solucionarmos nosso problema. Além do padrão, podemos utilizar como parâmetro para a função uma variável que guarde a distância percorrida para chegar no vértice atual , partindo de certa raiz , que basicamente nos diz a distância de pra , justamente por só haver um caminho entre e . Portanto, se utilizarmos o vértice do enunciado como a raiz da nossa , saberemos a distância de pra assim que visitarmos o vértice na .
Complexidade padrão da em uma árvore: . Confira o código abaixo para melhor entendimento: