Изменения

Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь у них = 1)

Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t после первого bfs, очевидно что ей в пару надо сапоставить вершину p , что dist(t, p) - max . Очевидно, что проблема решается запуском bfs из t.

'''Оценка производительности:'''

Все операции кроме bfs - О(1)

BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E)