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

Question

Вот проблема из книги «Алгоритмы» Вазирани

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

СОВЕТ: Это очень похоже на проблему поиска наибольшего независимого набора в дереве.

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

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

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

эта проблема похожа на эту тему , но нет определенного ответа.

Answer 1

Эта проблема в значительной степени эквивалентна проблеме подпоследовательности минимальной суммы , и может быть решена аналогичным образом с помощью динамического программирования.

Мы рассчитаем следующие массивы с помощью поиска в DF:

dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
         a path that is edge-disjoint relative to the path found for dw1[i].

Если вы можете рассчитать их, возьмите min(dw1[k], dw1[k] + dw2[k]) за все k.Это потому, что ваш путь примет одну из следующих основных форм:

  k              k
  |     or     /   \
  |           /     \
  | 

Все они покрыты суммами, которые мы берем.

Расчет dw1

Запустите DFS из корневого узла.В DFS отслеживайте текущий узел и его отца.Предположим, что в каждом узле его дочерние элементы равны d1, d2, ... dk.Тогда dw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]}).Установите dw1[i] = 0 для листовых узлов.Не забудьте обновить pw1[i] с выбранным предшественником.

Расчет dw2

Запустите DFS из корневого узла.Сделайте то же самое, что вы сделали для dw1, за исключением того, что при переходе от узла i к одному из его дочерних элементов k обновите dw2[i], только если pw1[i] != k.Однако вы вызываете функцию рекурсивно для всех детей.В псевдокоде это будет выглядеть примерно так:

df(node, father)
    dw2[node] = inf
    for all children k of node
        df(k, node)

        if pw1[node] != k
            dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])