Максимальная сумма расстояний узла до каждого другого узла

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

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

Примеры:

Input: N = 5, edges = { {0, 2}, {1, 3}, {0, 1}, {3, 4} }

Output: 10
Explanation:
Considering the node 2 as the sources node, the distances of all other nodes from node 2 are: 1(node 0), 2(node 1), 3(node 3), 4(node 4). Therefore, the sum of distances is 1 + 2 + 3 + 4 = 10.

Input: N = 6, edges[][] = {{0, 1}, {0, 2}, {2, 3}, {2, 4}, {2, 5}}

Output: 12

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, заметив, что существует связь между суммой расстояний узлов до всех остальных узлов. Возьмем узел х . Если y является его дочерним элементом, то наблюдается, что сумма расстояний y и x связана как;

distance of y = distance x – number of nodes in subtree y + nodes that are not in the subtree y

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

  • Определите функцию dfs(int s, vector<vector<int> > graph, int p, int d, int &ans, vector<int>& count) и выполните следующие шаги:
    • Перебрать диапазон [0, graph[s]] , используя переменную i , и если i не равно p, то увеличить значение ans на d и вызвать функцию dfs(i, graph, s, d + 1, ans , count) для изучения других узлов и установки значения count[s] как (count[s] + count[i]) .
  • Определите функцию dfs2(int s, vector<vector<int> > graph, int p, vector<int> &pd_all, int N, vector<int>& count) и выполните следующие шаги:
    • Перебрать диапазон [0, graph[s]] с использованием переменной i и, если i не равно p, установить значение pd_all[i] как (pd_all[s] – count[i] + n – count[ i]) и вызовите функцию dfs(i, graph, s, pd_all, N, count), чтобы найти ответ для других узлов.
  • Инициализируйте переменную, скажем, ans , в которой хранится результат.
  • Постройте список смежности, график [] из заданных ребер [][].
  • Инициализируйте вектор count[] размера N , чтобы отслеживать количество узлов в поддереве данного узла.
  • Инициализируйте переменную pd_0 как 0 , чтобы сохранить сумму расстояний от узла 0 до всех остальных узлов в дереве.
  • Вызовите функцию dfs(s, graph, p, d, ans, count), чтобы найти требуемое расстояние от узла 0 до каждого другого узла и сохранить количество узлов в поддереве.
  • Инициализируйте вектор pd_all[] размера N , чтобы хранить расстояния от каждого другого узла.
  • Установите значение pd_all[0] как pd_0 .
  • Вызовите функцию dfs2(s, graph, p, pd_all, N, count), чтобы найти необходимые расстояния от каждого другого узла.
  • Переберите диапазон [0, N], используя переменную i , и обновите значение ans как максимальное значение ans или pd_all[i] .
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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


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

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