Задача B3. Оптические каналы связи

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как pi.

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом pi, равна wi. Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам.

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

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

Формат входных данных

На первой строке ввода находятся два целых числа n и k (2 ≤ n ≤ 105, 1 ≤ k ≤ 100).

На следующих n − 1 строках заданы описания каналов, (i − 1)-я из этих строк содержит два целых числа: pi и wi (1 ≤ pi ≤ i, 0 ≤ wi ≤ 109).

Формат выходных данных

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

Ограничения

2 ≤ n ≤ 105, 1 ≤ k ≤ 100

1 ≤ pi ≤ i, 0 ≤ wi ≤ 109

Система оценки

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
15n ≤ 15, k = 1, wi = 0первая ошибка
25n ≤ 15, wi = 01первая ошибка
33n ≤ 151, 2первая ошибка
47k = 1, wi = 01первая ошибка
55k = 11, 4первая ошибка
67k ≤ 2, wi = 01, 4первая ошибка
74k ≤ 21, 4, 5, 6первая ошибка
811n ≤ 100, wi = 01, 2первая ошибка
94n ≤ 1001, 2, 3, 8первая ошибка
1011n ≤ 2 000, wi = 01, 2, 8первая ошибка
114n ≤ 2 0001, 2, 3, 8, 9, 10 первая ошибка
1220wi = 01, 2, 4, 6, 8, 10первая ошибка
13141 — 12первая ошибка

Пояснение к примеру

Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна 0 и не показана.

Есть и другие подходящие решения, в которых модернизируется 4 канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.

Примеры тестов

Стандартный вход Стандартный выход
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

0.423s 0.011s 17