Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на максимального веса в дереве=====Формулировка===Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. То есть необходимо решить задачу о максимальном взвешенном паросочетании.
===Решение=={{Определение | definition =Множество рёбер графа, такое, что у любых двух рёбер нет общей вершины, называется [[Файл:parosochetanie.png|100px|right|frameТеорема_о_максимальном_паросочетании_и_дополняющих_цепях |Максимальное взвешенное паросочетаниепаросочетанием]].Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.
Если мы запрещаемПусть задано взвешенное дерево, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детямс весами, обозначенными как <tex>w_{i,j}</tex>, где <tex>i</tex> и <tex>j</tex> — вершины дерева, соединённые ребром. В ином случае мы можем разрешить не всем детямЗадача: составить такое паросочетание, а только темчтобы суммарный вес всех рёбер, которые не были выбраны ребром из корнявходящих в него, был максимальным.
===Рекуррентная формула===Обозначим в качестве Для решения данной задачи существует несколько алгоритмов. Например, [[алгоритм_Куна_для_поиска_максимального_паросочетания | алгоритм Куна]], который имеет верхнюю оценку порядка <tex>dpO \left (vertex, usen^3 \_rootright )</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.Если <tex>use\_root=1</tex>Но так как нам дано дерево, то в этом поддереве мы разрешаем занимать кореньможно использовать динамическое программирование, иначе нет. Обозначим вес ребра из время работы алгоритма с которым улучшается до <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]O \left ( n \right )</tex>.
Обозначим <tex>dp(ua[i]</tex> как паросочетание максимального веса в поддереве с корнем в i-той вершине, при этом i-тая вершина соединена ребром, входящим в паросочетание, 0) = \sum_{\text{child}\ v\ of\ u}dp(vс вершиной, 1)входящей в поддерево i-ой вершины; аналогично </tex>b[i]<br/tex>- как паросочетание максимального веса в поддерева с корнем в i-той вершине, но только при этом i-тая вершина соединена ребром, входящим в паросочетание, с вершиной, не входящей в поддерево i-ой вершины; а <tex>dp(u, 1) c[i]= \max\left\{dp(ua[i], 0b[i] \right )</tex>,\ \max_{\text{child}\ x\ of\ u}\{dp(xтаким образом, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ wответ на задачу будет находиться в <tex>c[uroot]</tex>, x] \}\right\}где <tex>root</tex>- корень дерева. Идея динамического программирования здесь состоит в том, что для того, чтобы найти паросочетание максимального веса с корнем в вершине i, нам необходимо найти максимальное паросочетание для всех поддеревьев i-ой вершины.
Заметим, что вторую формулу можно упростить:<br><tex>\sum_{\text{child}\ v\ of\ u; \ v \ne Обозначим Ch(x }dp(v, 1) = dp(u, 0) - dp(— как множество сыновей вершины x, 1)</tex>и будем находить значения ''a'' и ''b'' следующим образом:
Теперь наши формулы имеют вид:<br><tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(vЕсли вершина x — лист, 1)то </tex><br><tex>dp(u, 1) a[x]= \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ wb[u,x] \}\right\}=0</tex>,
Заметимв противном же случае * <tex>a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y} +\sum_{\substack{z \neq y\\z \in Ch(x)}} \limits \max \left ( a[z],b[z] \right )\right )</tex>,* <tex>b[x]=\sum_{z \in Ch(x)} \limits \max \left ( a[z], b[z] \right )</tex> С учётом того, что с помощью этого преобразования мы сократили общее время вычисления с <tex>Oc[i]=\max \left ( a[i],b[i] \right )</tex>, эти формулы можно переписать как * <tex>a[x]=\max_{y \in Ch(x)}\limits \left ( b[y]+w_{x,y}-c[y] \right )+b[x]</tex>* <tex>b[x]=\sum_{z \in Ch(x)} \limits c[z]</tex>. Теперь оценим количество операций, необходимых нам для нахождения <tex>c[root]</tex>. Так как <tex>c[i]=\max \left (n^2a[i],b[i] \right )</tex> до , то для вычисления <tex>c[root]</tex> необходимо вычислить <tex>a[root]</tex>, <tex>b[root]</tex>. Для вычисления и того, и другого необходимо время порядка <tex>O\left ( \sum_{x=1}^n \limits \left | Ch(x) \right | \right )=O \left (n\right )</tex>, где n — количество вершин в дереве.
===Реализация===
