Сумма длин путей от каждого узла ко всем другим узлам с использованием метода переукоренения дерева.

Для каждого узла в неориентированном дереве найдите сумму длин путей от него ко всем другим узлам, используя метод переукоренения дерева.

Rerooting is a dynamic programming technique in trees. Using this a property dp[i] on tree is calculated, when the tree is rooted at i.

Пример:

Input: Consider the tree shown in the image:

tree rooted at 1 (arrow represent paths from root to other nodes)

Output: 12 9 17 14 10 15 15

Explanation: for node i : i1 + i2 + i3 . . . in, where ij is length of path from i to j
For node 1 : 0 + 1 + 1 + 2 + 2 + 3 + 3 = 12
For node 2 : 1 + 0 + 2 + 1 + 1 + 2 + 2 = 9
For node 3 : 1 + 2 + 0 + 3 + 3 + 4 + 4 = 17
For node 4 : 2 + 1 + 3 + 0 + 2 + 3 + 3 = 14
For node 5 : 2 + 1 + 3 + 2 + 0 + 1 + 1 = 10
For node 6 : 3 + 2 + 4 + 3 + 1 + 0 + 2 = 15
For node 7 : 3 + 2 + 4 + 3 + 1 + 2 + 0 = 15

Наивный подход: этот подход основан на следующем наблюдении за динамическим программированием.

Рассмотрим следующий рисунок, чтобы понять переход в динамическом программировании:

Illustration:

tree dp for sum of path lengths

Note: dp[node] in figure denotes the sum of paths from node to all its subtrees.

Now Consider child ‘b’ of node ‘a’, 

1. Size of subtree ‘b’, size[b] and the sum of lengths of paths for subtree ‘b’ is given as dp[b].
2. Consider all the paths which start at ‘a’ and end at some node in subtree of ‘b’.
3. Every path can be broken down as follows: path(a, x) = edge(a, b) + path(b, x)
4. As lengths of all paths of form path(b, x) is already covered in dp[b], only the edge(a, b) needs to be added for all nodes ‘x’ in subtree of ‘b’.
5. That means size[b] needs to be added to dp[b], hence the contribution of subtree ‘b’ to dp[a] is (dp[b] + size[b]).

Переходы следующие:

Transition :
for (child of node):
    dp[node] += dp[child] + size[child]

Выполните шаги, указанные ниже, чтобы реализовать подход:

1. Для каждого узла выполните следующие действия:
   • Укорените дерево в этом узле и найдите dp, как описано выше.
2. Поскольку дерево находится в корневом узле , все остальные узлы будут в его поддереве. Таким образом, dp[node] будет требуемым ответом для 'node' .

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

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

Посмотрите на следующий рисунок, чтобы понять концепцию повторного рутирования:

Примечание: на приведенном выше рисунке ребра ненаправлены, стрелки представляют только пути от корня к другим узлам.

• На данном рисунке происходит перепрошивка с «1» на «2» с использованием следующего подхода.
  • удалить 2 из детей 1
  • добавить 1 к детям 2

Поскольку нет пересчета для каждого узла, а переукоренение занимает всего O (1), общая временная сложность также уменьшается.

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