Взлом сети

Здесь дано дерево и нужно выбрать покрывающее множество минимальной стоимости.

Подвесим дерево за какую-то вершину (например, первую). Теперь пусть f(i,0) - наименьшая стоимость покрытия поддерева с корнем в i, если мы не добавляем вершину i в покрытие и f(i,1) - то же самое, если мы добавляем вершину i в покрытие. Тогда справедливы следующие рекуррентные соотношения:

f(i,0)=sum{f(j,1)}, где j пробегает по всем потомкам вершины i
f(i,1)=cost(i)+sum{ min{f(j,0),f(j,1)} }, где j пробегает по всем потомкам вершины i

Тогда ответ на задачу это min{f(1,0),f(1,1)}.