Найдите минимальное значение, необходимое для обнуления всех узлов дерева, увеличивая соседние узлы на каждом шаге

Question

1. Проблема в том, чтобы найти минимальное значение, необходимое для обнуления всех узлов, назовем его K.

2. Дается недвоичное дерево чисел.

3. На первом шаге вы можете выбрать один из узлов для начала.Если K больше значения этого узла, вы изменяете это значение на ноль и увеличиваете значение других узлов, которые находятся на расстоянии одного или двух.Обратите внимание, что как только значение узла становится равным нулю, оно больше не будет увеличиваться, и оно не позволит увеличивать присоединенных к нему узлы.

4. Затем следует выбрать другой узел, который имеет по крайней мереодин узел с нулевым значением на расстоянии один, и повторите процесс

Пример:

5
 \
  2 
   \
    5

когда мы начнем с листа со значением 5, у нас будет

6
 \
  3
   \
    0

Тогда мы должны выбрать 3;мы не можем выбрать 6, потому что у него нет нулевого узла на расстоянии один!

7
 \
  0
   \
    0

В конце мы выбираем 7 и K = 7, но если сначала мы выберем 2, то получим:

6
 \
  0
   \
    6

Тогда мы должны выбрать 6;поскольку узел со значением два теперь равен нулю, соединение разрывается, и при изменении значения узла со значением шесть больше никакого увеличения не произойдет!

0
 \
  0
   \
    6

Таким образом, минимальное значение K = 6

Мой текущий подход:

1. Найдите максимальный узел и начните с него (если имеется болеевыбран один максимальный узел, тот, который приходит раньше)

2. Я определяю массив, назовем его возможных узлов , и я добавляю узел, найденный на шаге 1

3. Пока возможных узлов не пусто, я выполняю следующие шаги:

   a.Выберите максимальное значение в возможных узлах;давайте назовем это max_node

   b.Сделайте max_node power zero и обновите K

   c.Увеличьте значение его родителя, прародителя, детей, внуков и братьев и сестер (если раньше они не были равны нулю)

   d.Добавьте своих родителей и потомков с ненулевыми значениями к возможным узлам

   e.Удалите max_node из возможных узлов

На самом деле это проблема с домашним заданием, но этот подход не правильный!Он дает неправильные ответы и ограничивает время ожидания.

Ограничения

• Количество узлов ≤ 3 × 10 ⁵

• -10 ⁹ ≤ значение узлов ≤ 10 ⁹

• Ограничение времени: 2,5 секунды

• Ограничение памяти: 256 МБ

Answer 1

Если вы начинаете со случайного узла в дереве, то K является максимумом:

1. начальный узел
2. его дети + 1
3. его родитель + 1
4. все остальные узлы + 2

Это связано с тем ограничением, что вы можете выбирать только узлы с 0-узлами рядом с ним и что они не увеличиваются.

Мы можем заключить, что Kmin должен быть между max и max + 2.

Таким образом, алгоритм O (n) может выглядеть так:

1. найдите максимальное значение узла max и посчитайте, сколько узлов имеют это значение => maxCount
2. если maxCount = 1, то посчитать, сколько узлов имеют значение max - 1 => max1Count, есть две возможности:
   1. max1Count = 0 или число смежных узлов со значением max - 1 к узлу со значением max равно max1Count => решение max
   2. в противном случае решение max + 1
3. найти все узлы со значением max, которые находятся выше в дереве:
   1. если вы нашли только один узел для глубины первого вхождения max:
      1. количество детей со значением max равно maxCount - 1 => решение max + 1
      2. есть только один дочерний элемент со значением max, и число его дочерних элементов со значением max равно maxCount - 2 => решение max + 1 тоже
      3. нет дочерних элементов со значением max, но есть maxCount - 1 внуков, у которых у всех один и тот же родительский элемент и значение max => решение max + 1 также
      4. в противном случае решение будет max + 2
   2. , если вы нашли maxCount узлов, и все они имеют одного и того же родителя => решение - max + 1
   3. в противном случае решение будет max + 2