47
правок
Изменения
→Рекуррентная формула
<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>
Заметим, что вторую формулу можно упростить:<br>
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>
Теперь наши формулы имеют вид:<br>
<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)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u] \}\right\}</tex>
Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.
===Псевдокод===
