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

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

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

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