Анонс #118. Сумма на дереве

Задача: дано дерево состоящее из N вершин, каждая вершина имеет значение value. Необходимо определить такое множество вершин дерева, в котором никакие две вершины не имеет общего ребра, и сумма значений в этих вершинах максимальная. Выведите максимально возможную сумму значений в таком множестве вершин.

Входные данные: edges - список ребер, которым задано дерево; каждое ребро определятся двумя вершинами: (i, j).

value - упорядоченный массив значений (от 0 до 1000) в вершинах, где value(i) - значение вершины i (i от 1 до N; 1 <= N <= 10^4).

Вывод: максимальную сумму значений вершин в подмножестве.

Пример:

Edges = [ (1, 2), (1, 3), (2, 4) ]

Value = [ 1, 1, 0, 1] (Пояснение: 1я вершина - значение 1; 2я вершина - 1; 3я вершина - 0; 4я вершина - 1)

Answer = 2