Дистанционный практикум по программированию

Компьютерная сеть Пентагона состоит из N компьютеров, некоторые из которых соединены прямыми двусторонними каналами связи. В целях повышения секретности при проектировании сети количество каналов связи было сокращено до минимума с тем условием, чтобы любые два компьютера имели возможность обмена информацией либо непосредственно, либо через другие компьютеры сети.

КГБ хочет прослушивать все передаваемые в сети Пентагона сообщения. Для этого советскими программистами был разработан вирус, который, будучи установлен на какой-либо из компьютеров, передает КГБ всю информацию, проходящую через него. Оказалось что материальные затраты, необходимые для установки вируса на различные компьютеры, различны. Требуется определить набор компьютеров, которые КГБ должно инфицировать, чтобы минимизировать общие материальные затраты.

Исходные данные

Первая строка входного файла содержит N - количество компьютеров в сети (1<=N<=500) . В i-ой из последующих строк N содержатся номера компьютеров, с которыми непосредственно связан компьютер i. Далее следует N целых чисел из диапазона [1, 1000] - материальные затраты, связанные с установкой вируса на каждый из компьютеров.

Результат

В выходной файл выведите минимально возможные материальные затраты и список номеров компьютеров, которые нужно инфицировать, упорядоченный по возрастанию.

Пример

5
5
4
4
2 3 5
4 1
1 5 5 2 10

3 
1 4

Комментарии

Динамическое программирование на дереве.

Первый абзац условия задачи в результате формализации сводится к словам <задано дерево с N вершинами>, второй - <найти доминирующее над ребрами множество вершин минимального веса>. Выберем какую-нибудь вершину заданного дерева в качестве корня и подвесим дерево за эту вершину. Для каждого поддерева определим пару чисел (a, b) , где a равняется ответу на нашу задачу для этого поддерева, а b - ответом на ту же задачу с дополнительным требованием включения корня рассматриваемого поддерева в искомое множество.

Эти пары чисел (a, b) вычисляются динамически по высоте поддеревьев. Для дерева, состоящего из единственной вершины, a - равно нулю, а b - весу этой вершины. Теперь покажем, как вычислить числа a и b для дерева, состоящего из большего числа вершин. Его корень имеет какое-либо количество поддеревьев, для которых пары чисел (a, b) уже подсчитаны. Ясно, что число b равно сумме всех чисел a_i, увеличенной на вес корня рассматриваемого дерева. Число a, в свою очередь, равно минимуму из суммы чисел b_i и b.

Описанная процедура легко реализуется рекурсивным алгоритмом.