Изменения
Нет описания правки
}}
Мы свели задачу к нахождению вершины v<tex>w</tex>, такой, что сумма глубин поддеревьев максимальна.
Докажем, что одно из искомых поддеревьев содержит самый глубокий лист.
Пусть нет, тогда взяв расстояние от v <tex>w</tex> до глубочайшего листа мы можем улучшить ответ.
Таким образом мы доказали, что нам нужно взять наиглубочайшую вершину t <tex>u</tex> с наибольшей глубиной после первого bfs, очевидно что ей в пару надо сапоставить сопоставить вершину p <tex>w</tex> , что dist(tu, pw) - <tex>max </tex> . Очевидно, что проблема решается запуском bfs из t<tex>u</tex>.
