Re: Поиск самых отдалённых вершин в дереве
Вот контрпример(первые 2 числа - номера вершин, соединяемых ребром, 3-е - вес)
1 2 -1
2 3 -100
3 4 10
Если мы сделаем поиск от вершины 1, то самая дальняя будет 2, а самый длинный путь между 3 и 4.
Re: Поиск самых отдалённых вершин в дереве
Так а что тут непонятного?
Когда рёбра просто дробные то это ниначто не влияет.
А вот когда рёбра и отрицательные могут быть,то происходит та же проблема что и при пуске дейкстры по графу с отрицательными рёбрами^_^
КАДР а тут динамика не покатит? Вроде динамике то пофигу.
Re: Поиск самых отдалённых вершин в дереве
Динамика то покатит(с маленьким изменением), а вот дфс от какой-то вершины, а потом еще один дфс из самой дальней уже не прокатит. Насколько я понял, вопрос был именно о втором.
Re: Поиск самых отдалённых вершин в дереве
Да! Но я просто выразил мнение как ещё можно решить её за линейно 
А какое хоть изменение :%?
Re: Поиск самых отдалённых вершин в дереве
Ну нам нужно добавить ограничение, что длина пути, заканчивающегося в корне поддерева должна быть неотрицательной, т.к. иначе мы просто можем вместо этого пути стартовать с данной вершины и это только улучшит ответ.
Re: Поиск самых отдалённых вершин в дереве
А ну да Динамика рулит!