Как найти кратчайший простой путь в дереве за линейное время?

Задача из книги «Алгоритмы» Вазирани

. Входными данными для этой задачи является дерево T с целыми весами на краях. Вес может быть отрицательным, ноль или положительный. Приведите алгоритм с линейным временем, чтобы найти кратчайший простой путь в T. Длина path - это сумма весов ребер в пути. Путь является простым, если ни одна вершина не повторяется. Запись что конечные точки пути не ограничены.

ПОДСКАЗКА: Это очень похоже на проблему поиска наибольшего независимого множества в дереве.

Как я могу решить эту проблему за линейное время?

Вот мой алгоритм, но мне интересно, линейное ли это время, поскольку оно ничем не отличается от сначала в глубину:

1. Дерево обхода (сначала в глубину)
2. Сохранять индексы (узлы)
3. добавлять значения
4. делать (1) до конца дерева
5. сравните сумму и выведите путь и сумму

эта задача аналогична этой теме , но нет определенного ответа.