ACMP 604
(перенаправлено с «Интернет-олимпиада 28.01.2006, усложнённый уровень, A»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Вид подзадачи: d[v] — количество способов сделать кактус из поддерева с корнем в вершине v.
Рекуррентная формула: Рассмотреть три случая: рёбра не добавляются, добавляется ребро из v в некоторого потомка, добавляется перекрёстное ребро между потомками из различных поддеревьев.