Найдите MEX каждого поддерева в данном дереве

Опубликовано: 21 Сентября, 2022

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

The MEX value of node V is defined as the smallest missing positive number in a tree rooted at node V.

Примеры:

Input: N = 6, edges = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {3, 5}}, val[] = {4, 3, 5, 1, 0, 2}
Output: [6, 0, 0, 3, 1, 0]
Explanation:
             0(4)
           /    
      1(3)    3(1)
     /         /    
2(5)     4(0)   5(2)  

In the subtrees of:
Node 0: All the values in range [0, 5] are present, hence the smallest non-negative value not present is 6.
Node 1: The smallest non-negative value not present in subtree of node 1 is 0.
Node 2: The smallest non-negative value not present in subtree of node 2 absent is 0.
Node 3: All the values in range [0, 2] are present, hence the smallest non-negative value not present in subtree of node 3 is 3.
Node 4: The smallest non-negative value not present in subtree of node 4 is 1.
Node 5: The smallest non-negative value not present in subtree of node 5 is 0.

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

  • Инициализируйте массив, скажем, sol[] для хранения MEX для каждого узла.
  • Выполните обход DFS с узла 0 и выполните следующие шаги:
    • Сохраните все узлы во время DFS для каждого узла в векторе.
    • Объедините два вектора в отсортированном порядке для каждого узла в рекурсивных вызовах.
    • Примените двоичный поиск в отсортированном списке, чтобы найти наименьшее неотрицательное целочисленное значение, которого нет в отсортированном массиве, и сохраните значение MEX текущего поддерева в массиве sol[] .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение, хранящееся в массиве sol[] .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ