Максимизируйте сумму путей от LCA узлов u и v до одного из этих узлов

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

Для дерева, состоящего из N узлов, массив ребер [][3] размера N – 1 такой, что для каждого {X, Y, W} в ребрах [] существует ребро между узлом X и узлом Y с весом W и два узла u и v , задача состоит в том, чтобы найти максимальную сумму весов ребер на пути от младшего общего предка (LCA) узлов (u, v) до узла u и узла v .

Примеры:

Input: N = 7, edges[][] = {{1, 2, 2}, {1, 3, 3}, {3, 4, 4}, {4, 6, 5}, {3, 5, 7}, {5, 7, 6}}, u = 6, v = 5
Output: 9
Explanation:

The path sum from node 3 to node 5 is 7.
The path sum from node 3 to node 6 is 4 + 5 = 9.
Therefore, the maximum among the two paths is 9.

Input: N = 4, edges[][] = {{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, u = 1, v = 4
Output: 12

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

  • Создайте дерево из заданного ввода ребер.
  • Найдите LCA для заданных узлов u и v , используя подход, обсуждаемый в этой статье.
  • Выполните поиск в глубину, чтобы найти сумму путей, т. е. сумму весов ребер на пути от LCA до узлов u и v , и сохраните ее в переменных, скажем, maxPath1 и maxPath2 соответственно.
  • После выполнения вышеуказанных шагов выведите в качестве результата максимум maxPath1 и maxPath2 .

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

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

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