Минимизируйте операции по преобразованию каждого узла N-арного дерева из начального [i] в конечное [i] путем переворачивания поддерева текущего узла альтернативным способом.

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

Примеры:

Input: N = 3, edges = {{1, 2}, {1, 3}}, initial[] = {1, 1, 0}, final[] = {0, 1, 1}
      1(1)
     /    
2(1)   3(0)
Output: 2
Explanation:
Operation 1: Pick the node 1 and flips its initial values. After this operation initial[] = {0, 1, 0} and final[] = {0, 1, 1}.
Operation 2: Pick the node 3 and flips its initial values. After this operation initial[] = {0, 1, 1} and final[] = {0, 1, 1}.
Therefore, print 2 as the minimum number of operations.

Input: N = 1, edges = [], initial[] = {0}, final[] = {1}
Output: 1

Подход: данная проблема может быть решена путем выполнения обхода DFS в данном дереве и обновления значения узлов в массиве initial[] альтернативным способом. Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте переменную, скажем, total как 0 , чтобы сохранить количество необходимых операций.
• Выполните обход DFS, отслеживая две логические переменные (первоначально как false ), которые будут меняться только при перевороте, и выполните следующие шаги:
  • Пометить текущий узел как посещенный узел.
  • Если значение побитового исключающего ИЛИ начального значения текущего узла, конечного значения текущего узла и текущей логической переменной не равно нулю, то инвертировать текущую логическую переменную и увеличить значение итога на 1 .
  • Пройдите все непосещенные дочерние узлы текущего узла и рекурсивно вызовите обход DFS для дочернего узла.
• После выполнения вышеуказанных шагов выведите значение итога в качестве результата.

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

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