Минимум ходов, чтобы сделать узлы дерева неотрицательными

Дано дерево, состоящее из N узлов, где значение каждого узла является отрицательным числом его узла (т. е. 1-й узел имеет значение -1, 2-й узел имеет значение -2 и т. д.) и родительский массив Par [] , который хранит родительский узел i- ^го узла. Вы можете выбрать любой узел из дерева и добавить 1 ко всем узлам на пути от корня дерева к этому конкретному узлу. Задача состоит в том, чтобы найти минимальное количество операций, чтобы все значения дерева стали неотрицательными.

Примечание. В родительском массиве используется индексация с отсчетом от 1. Корнем дерева является узел 1, поэтому его родитель помечен как -1 в родительском массиве.

Примеры:

Input: N = 5, Par[] = {-1, 1, 2, 2, 4}
Output: 8
Explanation: Choose 3 as node three times and 5 as node five times. The following tree can be constructed using a parent array. -1 is treated as root.
          1 
        /
     2
  /  
3    4
       
        5

Input: N = 3, Par[] = {-1, 3, 1}
Output:  3
Explanation: Choose 2 as node three times. Given tree looks like
    1
    |
   3
   |
  2

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

To make i^th node non-negative, we have to increment at least i times. So the optimal way is to increment the values of a path such that the increment operation does not exceed the maximum value along the path.

Для реализации идеи выполните следующие шаги:

• Создайте список смежности adj[] для хранения в нем дерева.
• Теперь используйте DFS для обхода дерева и для каждого узла рассмотрите максимальное значение узла и сумму результатов дочерних узлов как минимальные операции для этого узла.
• В конце концов, корневой узел получит результат для всего дерева.

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

Сложность времени: O(V+E), где V — количество узлов в дереве, а E — количество ребер.
Вспомогательное пространство: O(V), где V — количество узлов в дереве.

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

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