Резка кромок в деревьях

Question

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

Функция должна печатать минимальную разницу, которую он обнаружил для стандартного вывода (стандартный вывод).

Функция получит следующие аргументы:

parent, который представляет собой массив из целых чисел со следующим значением: parent[i] = родитель узла i (более конкретно его ID)

parent[i] = -1, если я есть ни один родитель (я не корень дерева)

ограничения данных

Максимальное число узлов в дереве составляет 50000

Эффективность ограничения

Функция, как ожидается, чтобы распечатать результат менее чем за 2 секунды

Пример

Input parent: [1, 4, 4, 2, -1, 2, 2] 

aka :   4 
      /\ 
      1 2 
      // | \ 
      0 3 5 6 

Output: 9 

Объяснение: Мы удаляем край между узлами 2 и 6.

Answer 1

1. Для каждого узла вычислите сумму своих дочерних элементов, затем добавьте это значение к себе и сохраните его в узле. Назовем это значение S_n, где n - это узел. (Может быть легко сделать с помощью рекурсии & после заказа обхода)

2. Найти узел n которого S_n имеет минимальную разницу в S_root/2. Край между n и его родителем - это край, который мы хотим. (Это требует линейного времени в худшем случае.)