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

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.

Независимый набор из красных вершин

Определение:

Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).