Динамическое программирование (DP) — это техника решения задач путём разбиения их на перекрывающиеся подзадачи с оптимальной подструктурой. Существует множество задач, использующих DP, таких как сумма подмножества, рюкзак, сдача монет и т.д. DP также может применяться к деревьям для решения некоторых конкретных задач.
Пример базового поддерева DP
Дано дерево с N узлами и N−1 рёбрами. Требуется найти максимальную сумму значений узлов на пути от корня до некоторого листа без повторного посещения узлов.
На рисунке выше показано дерево с N=14 узлами и значениями:
Жадный подход здесь не работает: выбор локально максимальных значений (3→10→5) даёт путь 7 с суммой 18, что не оптимально.
Идея решения
Используем DP на дереве.
Пусть:
DPi=максимальнаясуммапутиотiдолюбоголиста
Тогда:
для листа: DPi=valuei
для внутреннего узла:
DPi=valuei+u∈children(i)maxDPu
Вычисление выполняется DFS снизу вверх.
Начинаем с листьев и поднимаемся вверх, каждый раз добавляя максимум из поддерева к текущему узлу. В конце DP1 содержит максимальную сумму пути от корня до листа.
Задача 1
Условие задачи
Дано дерево T из N узлов.
Каждый узел i содержит Ci монет.
Нужно выбрать подмножество узлов так, чтобы:
не было выбрано два соседних узла
сумма монет была максимальной
Решение
Эта задача аналогична задаче на массиве:
dp(i)=max(Ai+dp(i−2),dp(i−1))
В дереве состояние определяется поддеревом вершины.
Зафиксируем корень (например, 1).
Пусть dp(V) — ответ для поддерева вершины V.
Искомый ответ: dp(1).
Выбор вершины
Если выбираем вершину V:
нельзя выбирать её детей v1,…,vk
можно выбирать внуков
Если не выбираем V:
можно выбирать детей
DP-формулировка
Введём два состояния:
dp1(V) — максимум, если V включена
dp2(V) — максимум, если V не включена
Тогда:
dp1(V)=CV+u∈children(V)∑dp2(u)
dp2(V)=u∈children(V)∑max(dp1(u),dp2(u))
Ответ:
max(dp1(1),dp2(1))
Реализация
Задача 2
Постановка задачи
Дано дерево T из N узлов. Требуется вычислить длину самого длинного пути между любыми двумя узлами (диаметр дерева).
Решение
Зафиксируем корень дерева в узле 1.
Рассмотрим произвольную вершину x. Возможны два типа максимального пути:
Путь начинается в x и идёт вниз в его поддерево. Обозначим длину как f(x).
Путь проходит через x и соединяет два его поддерева. Обозначим длину как g(x).
Диаметр дерева равен:
xmaxmax(f(x),g(x))
Вычисление f(x)
Пусть вершина V имеет потомков v1,v2,…,vn.
По определению:
f(V)=1+max(f(v1),f(v2),…,f(vn))
Если потомков нет (лист):
f(V)=1
Это стандартная рекурсия Tree-DP: значение узла зависит от значений детей.
Вычисление g(x)
Путь может:
начинаться в поддереве vi
проходить через V
заканчиваться в поддереве vj, i=j
Чтобы максимизировать длину, выбираем два наибольших значения среди:
f(v1),f(v2),…,f(vn)
Тогда:
g(V)=2+(двемаксимальныевеличинысредиf(vi))
Итог
Для каждой вершины обновляем:
diameter=max(diameter,f(V),g(V))
Реализация
Задача 3
Постановка задачи
Дано дерево T из N узлов и целое число K.
Требуется найти количество различных связных поддеревьев размера не более K.
Решение
Сначала уточним определение.
Поддерево — это любое связное подмножество вершин исходного дерева.
Это отличается от стандартного поддерева вершины (включающего всех её потомков).
Как обычно в задачах на деревья, зафиксируем корень в узле 1.
Обозначим через S(V) стандартное поддерево вершины V
(все вершины в поддереве V).
Подсчёт всех поддеревьев
Сначала посчитаем число всех поддеревьев (без ограничения на размер).
Пусть:
f(V)=числоподдеревьеввнутриS(V),содержащихV
Если у V дети v1,v2,…,vn, то для каждого ребёнка есть два варианта:
не брать ничего из его поддерева
взять поддерево с корнем в vi
Поэтому:
f(V)=i=1∏n(1+f(vi))
Однако это считает только поддеревья с корнем в V.
Нужно также учитывать поддеревья, лежащие внутри потомков.
Введём:
g(V)=числоподдеревьеввS(V),несодержащихV
Тогда:
g(V)=u∈children(V)∑(f(u)+g(u))
Общее число поддеревьев в дереве:
f(1)+g(1)
Ограничение на размер ≤ K
Теперь требуется считать только поддеревья размера не более K.
Теперь давайте проанализируем сложность. На каждом узле с n детьми мы выполняем вычисление n⋅K2, поэтому общая сложность O(N⋅K2).
Оптимизация
Это очень полезная задача в мире соревновательного программирования. Решение, представленное в том блоге, имеет сложность O(n⋅K2), но мы хотим изменить её на O(n⋅K).
Обозначим Subv как размер поддерева вершины v.
Решение аналогично решению из того блога, и разница очень проста. Вам не нужно перебирать все значения K. Очевидно, что если i>Subv, то dp[v][i]=0. Так что каждый раз вам нужно перебирать значения min(K,Subv).
Код становится следующим образом:
Доказательство сложности
Сначала введём массив EnterTime. Если EnterTimev=x, то v — это x-я вершина, в которую мы вошли при обходе. Каждая вершина имеет stv, который является массивом, и в самом начале stv={v} для всех v. Позже мы изменяем этот набор, и мы посмотрим, как. Также считаем, что stv всегда упорядочен по EnterTime.
Мы хотим построить ориентированный граф H размером n. Когда мы собираемся обновить dp[v] от его дочерней вершины u, добавляем направленное ребро из каждой вершины в stu в каждую вершину в stv в графе H.
Затем обновим stv, добавив первые K−size(stv) вершин из stu (если size(stv)=K, то это игнорируется). Также удалим каждую вершину из stu.
Сложность равна количеству рёбер в H. Мы хотим доказать, что число рёбер в H не превышает n⋅(2K), доказав, что у каждой вершины в H не более 2K исходящих рёбер.
Согласно нашему определению, в любой момент времени для любой вершины v существует не более 1 вершины u такой, что v находится в stu. Рассмотрим последний набор w, который является stu, и мы собираемся обновить dp[v] от его дочерней вершины u. Предположим, что w находится на p-м месте в stu. Согласно нашему определению, рёбра, исходящие из w, — это рёбра к первым p−1 вершинам в stu.
Мы знаем, что p≤K, так что до сих пор число рёбер, исходящих из w, не более K. Когда мы обновляем dp[v], мы добавим к этому числу не более K. Значит, в этот момент w имеет не более 2K исходящих рёбер. Также мы рассмотрели stu как последний набор, в котором находится w. Следовательно, в будущем не будет других рёбер, исходящих из w.
Таким образом, мы доказали, что число рёбер в H не превышает n⋅(2K), поэтому сложность равна O(nK).
