ДП по поддеревьям

Идея

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

Пример задачи

Пусть задано взвешенное дерево, с весами $w_{i, j}$, где $i$ и $j$ — вершины дерева, соединённые ребром. Пусть вес паросочетания - сумма весов, написанных на ребрах. Необходимо составить паросочетание максимального веса в этом дереве.

Решение

Пусть $dp_{i, 0}$ - максимальное паросочетание в поддереве $i$-й вершины, если мы еще не брали ребро из $i$ вершины, $dp_{i, 1}$ — если взяли, тогда, как посчитать $dp_{i, 0}$ для вершины, $dp_{i, 0} = \sum\limits_{v \in sons(i)} max(dp_{v, 0}, dp_{v, 1})$, так как если мы не берем ребро из $i$ вершины вниз, то мы можем взять любой ответ для сыновей. $dp_{i, 0} = max_{j \ \in \ sons(i)} \sum\limits_{v \in sons(i), v != j} max(dp_{v, 0}, dp_{v, 1}) + w_{i, j} + dp_{j, 0}$, так как мы точно должны взять ребро из $i$ в какого-то сына, а вот для всех остальных вершин можем выбрать, что хотим

Другие задачи

• Сумма длин всех путей в дереве
• Диаметр

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin