Оптические каналы связи
(Время: 3 сек. Память: 512 Мб Сложность: 65%)
Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам
связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как pi.
Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом pi, равна wi. Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам.
Министерство связи Флатландии хочет составить такой план модернизации каналов, чтобы после его выполнения связность сети по оптическим каналам связи была как можно выше. Поэтому необходимо выбрать для модернизации как можно больше каналов. Но при этом стоимость модернизации желательно минимизировать, поэтому при равном количестве необходимо выбрать для модернизации каналы с минимальной суммарной стоимостью.
Помогите специалистам министерства выбрать каналы для модернизации.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и k (2 ≤ n ≤ 105, 1 ≤ k ≤ 100).
В следующих n−1 строках заданы описания каналов, (i−1)-я из этих строк содержит два целых числа: pi и wi (1 ≤ pi ≤ i, 0 ≤ wi ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа cnt и cost: максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0
| 4 0 |
| 2 | 8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6
| 6 27 |
Пояснение
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже.
Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число
каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна
0 и не показана.
Есть и другие подходящие решения, в которых модернизируется 4 канала.
Конфигурация сети во втором примере до и после модернизации показана на рисунке ниже.
Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число
каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом
с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
