U rešenju ćemo koristiti jednu poznatu lemu:

Neka su ~u~ i ~v~ dva čvora sa najvećim rastojanjem u stablu, jedan od čvorova koji je najdalji od čvora ~w~ je čvor ~u~ ili čvor ~v~.

Pronađimo dva dva čvora koja su najudaljenija u stablu. Neka su to ~u~ i ~v~. Tvrdimo da je najveće rastojanje izmedju dva čvora različite lepote jednako sa: ~max(max_{lepota(w) \neq lepota(u)}(dist(u,w)),max_{lepota(w) \neq lepota(v)}(dist(v,w)))~, tj. da je dovoljno da prođemo kroz sve čvorove i uzmemo najveće rastojanje od tog čvora do nekog od dva kraja dijametra koji je različite lepote.

Dokaz:

Dokazaćemo ovu tvrdnju analizaranjem slučajeva:

• ~u~ i ~v~ su različite lepote. Tada je tvrđenje trivijalno ispunjeno, jer je najveće rastojanje u stablu, baš rastojanje između ~u~ i ~v~, a oni su različite lepote, pa su validan izbor.
• ~u~ i ~v~ su iste lepote. Neka smo sada u čvoru ~x~. Ukoliko je ~x~ različite lepote od krajeva dijametra, po lemi važi da će kraj dijametra biti najudaljeniji čvor od čvora ~x~. Neka, je dalje ~x~ iste lepote kao krajevi dijametra. Posmatrajmo ~y~, takvo da je ~y~ najdalje od ~x~ i da su ~x~ i ~y~ različite lepote. Kako je ~y~ različite lepote od ~x~, a ~x~ iste lepote kao krajevi dijametra, to je ~y~ rayličite lepote od krajeva dijametra. Tad je po lemi rastojanje od ~y~ do nekog od dva kraja dijametra veće od rastojanja od ~y~ do ~x~, pa nije ni važno da li smo uračunali u rešenje rastojanje između ~x~ i ~y~.

Analiza složenosti:

Dva najudaljenija čvora je moguće pronaći koristeći dve pretrage stabla u dubinu, u složenosti ~O(n)~. Drugi deo zadatka, prolazak kroz sve čvorove i pronalazak najvećeg rastojanja od nekog čvora do jednog od krajeva dijametra različite boje je trivijalno ~O(n)~. Dakle, složenost rešenja je ~O(n)~.

Zadatak je preuzet sa ~\texttt{Moscow}~ ~\texttt{Autumn}~ ~\texttt{Workshop}~ ~\texttt{2019}~ ~\texttt{Day}~ ~\texttt{3}~.