Изменения

Перейти к: навигация, поиск

Динамика по поддеревьям

47 байт добавлено, 21:29, 13 января 2013
Рекуррентная формула
===Рекуррентная формула===
Обозначим в качестве <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>
47
правок

Навигация