Количество простых путей в данном дереве

Опубликовано: 26 Февраля, 2023

Даны дерево из N узлов, пронумерованных от 1 до N , и N-1 ребер, а также массив V[] длины N , обозначающий значение i -го узла (0 ≤ i ≤ n-1). Задача состоит в том, чтобы посчитать количество простых путей , начинающихся с узла 1.

A path is defined as a simple path if the frequency of the value of any one of the nodes in the path is at least half of the length of the path rounded down to the next greater integer. The length of a path from A to node B is the number of nodes you encounter in that unique path while going from A to B.

Пример:

Input: N = 5, Edges[][] = {{1, 2}, {2, 4}, {2, 5}, {5, 3}}, V[] = {7, 9, 9, 4, 8};
Output: 3
Explanation: ALL THE POSSIBLE PATHS ARE:

  • Path= 1, length of path = 1, maximum frequent element is with val 7 with frequency 1, 1 ≥ (1/2).
  • Path= 1->2, length of path = 2, maximum frequent element is with 7  with frequency 1, 1 ≥ (2/2).
  • Path= 1->2->5->3, length of path = 4, maximum frequent element is with val 9 with frequency 2, (2 ≥ 4/2).

Подход:

The idea is to use store the frequency of every node while traversing the path starting from the root node and check whether the frequency of the current node value is greater than equal to half of the length of the path.

Выполните следующие шаги, чтобы решить проблему:

  • Запустите dfs с узла 1.
  • Поддерживайте карту частот для хранения частоты значений всех значений элемента, поступающих в путь.
  • Сохраняйте переменную len, в которой хранится количество узлов в текущем узле.
  • Предположим, что максимальная частота (максимальное частое значение элемента) в узле x равна f, теперь максимальная частота в дочерних элементах (y) узла x равна max(f, Frequency[y]).
  • После повторения всех дочерних элементов узла частота текущего значения узла уменьшается перед возвратом из узла, поскольку этот узел больше не будет вносить вклад.

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

Временная сложность: O(N), посещение каждого узла один раз в дереве с N узлами
Вспомогательное пространство: O(N), карта частот для хранения частоты значения узла.

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