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>
