47
правок
Изменения
м
→Рекуррентная формула
===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_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(v, 1)</tex><br>
