47
правок
Изменения
→Рекуррентная формула
===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex> и использующего корень, если <tex>root=1</tex> и наоборот.
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 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)\ +\ a[u] \}\right\}</tex>
