Сборник Олпрогера

Переподвешивание или rerooting при дпшках на дереве

Еще одна достаточно простая в понимании идея, которая может помочь в тасках на деревья, в которой легко написать решение для фиксированного корня за O(N/NlogN/Nlog^2N...) и нужно посчитать значения дпшки для других корней.

Идея очень простая - пусть мы посчитали вначале решение для корня v и все вспомогательные дпшки для ее сыновей. Тогда давайте корректно пересчитаем все значения для соседа v - u. Вначале запушим в стэк значения дпшек для v и u, потом пересчитаем значение v через всех сыновей, кроме u, потом пересчитаем значение u через всех сыновей. Потом рекурсивно решим для поддерева u, вернемся назад и откатим через стэк изменений значения дпшки в u и v.

Еще почитать:
Задачки + пересказ
Видео на кфе

Задачки:
DIV3F
Лучше вначале решить версию D1
F-ка ABC
Еще одна DIV3F

Codeforces

Re-rooting Tree DP?

I am facing issues in questions in which Given is a tree with no fixed root, n<=1e5 . I can simply do the question if i traverse the tree for each node as root (n^2) but it gives TLE. I know i have to apply DP and rerooting concept.

👍11

www.tgoop.com/sbornik_olprog/47

1.97K views34 defective braincells, Feb 12, 2023 at 05:59

Переподвешивание или rerooting при дпшках на дереве

Еще одна достаточно простая в понимании идея, которая может помочь в тасках на деревья, в которой легко написать решение для фиксированного корня за O(N/NlogN/Nlog^2N...) и нужно посчитать значения дпшки для других корней.

Идея очень простая - пусть мы посчитали вначале решение для корня v и все вспомогательные дпшки для ее сыновей. Тогда давайте корректно пересчитаем все значения для соседа v - u. Вначале запушим в стэк значения дпшек для v и u, потом пересчитаем значение v через всех сыновей, кроме u, потом пересчитаем значение u через всех сыновей. Потом рекурсивно решим для поддерева u, вернемся назад и откатим через стэк изменений значения дпшки в u и v.

Еще почитать:
Задачки + пересказ
Видео на кфе

Задачки:
DIV3F
Лучше вначале решить версию D1
F-ка ABC
Еще одна DIV3F

BY Сборник Олпрогера