Изменения

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. так как они могут влиять на ответы в других поддеревьях.

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