Минимальная сумма набора узлов Дерева при заданных условиях

Опубликовано: 26 Февраля, 2023

Для дерева с N узлами и N-1 ребрами и массива arr[] , где arr[i] обозначает значение i -го узла, задача состоит в том, чтобы найти набор узлов, сумма значений которого минимальна, а все другие узлы вне набора имеют ребро по крайней мере с одним из узлов в наборе.

Примеры:

Input: N = 3, edges[] = { {0, 1}, {1, 2} }, arr[] = { 5, 12, 3}
Output: 8
Explanation: We can select set {0, 2}, now unselected node {1} is connected to a selected node. Sum of values of subset nodes = A[0]+A[2] = 5+3 = 8

Input: N = 4 edges[] = { {1, 0}, {3, 0}, {2, 3} }, A[] = { 3, 4, 20, 14}
Output: 17
Explanation: We can select subset {0, 3}. Now unselected node {1} has an edge with node {0} and unselected node{2} has an edge with node {3}. Sum of values of subset nodes = A[0] + A[3] = 3 + 14 = 17

Наивный подход: проблема может быть решена на основе следующей идеи:

For each node there are two choices – either to pick or not pick an element to be a part of the set.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Предположим, мы находимся в заданном узле x .
    • Теперь, если мы включим текущий узел x , то для его дочерних элементов мы можем либо взять его дочерний узел, либо оставить его.
    • Если мы не включаем текущий узел x , мы должны включить его дочерние элементы.
  • Теперь запустите dfs с любого узла (скажем, 0).
  • Инициализировать ans значением 0.
  • Поддерживать переменная (скажем, pick ) для данного dfs. который показывает, обязательно ли выбирать текущий узел или есть варианты.
    • Если pick = 1, включить текущий узел в ответ .
    • Если pick = 0, сначала вычислить ans , взяв текущий узел, а затем оставив его. Верните минимум двух возможных случаев.
  • Запустите dfs с любого начального узла.
  • Возвращает значение ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(2 N )
Вспомогательное пространство: O(N)

Эффективный подход: проблема может быть решена с помощью мемоизации, основанной на следующей идее:

From the above recursion it can be seen that the approach has some overlapping subproblems. Here each unique state can be represented using two variables – one for the index (say i) and the other for representing if the element is picked or not (say j).

Now, use this memoization in the above recursion to avoid repeated calculation of the same subproblem.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)

Статьи по Теме:

  • Введение в дерево — учебные пособия по структурам данных и алгоритмам
  • Что такое мемоизация? Полное руководство