47
правок
Изменения
→Динамика по поддеревьям
Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.* Запретить выбирать ребра из корня.
Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.
===Рекуррентная формула===
Обозначим в качестве <tex>dp(uvertex, rootuse\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.Если <tex>rootuse\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе , иначе нет.Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(wv, 1)</tex><br><tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ aw[u, x] \}\right\}</tex>
Заметим, что вторую формулу можно упростить:<br>
Теперь наши формулы имеют вид:<br>
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(wv, 1)</tex><br>
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>
dp[v][root] = max1
return dp[v][root]
==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]
