Изменения
Нет описания правки
Будем пользоваться свойством,что в любом дереве >= 2 висячих вершин(степерь у них = 1)
Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t после первого bfs, очевидно что ей в пару надо сапоставить вершину p , что dist(t, p) - max . Очевидно, что проблема решается запуском bfs из t.
}}
'''Оценка производительности:'''
Все операции кроме bfs - О(1)
BFS работает линейное время,запускаем мы его 2 раза.Получаем O(V+E)