Задача 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
Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 5 | n ≤ 15, k = 1, wi = 0 | первая ошибка | |
| 2 | 5 | n ≤ 15, wi = 0 | 1 | первая ошибка |
| 3 | 3 | n ≤ 15 | 1, 2 | первая ошибка |
| 4 | 7 | k = 1, wi = 0 | 1 | первая ошибка |
| 5 | 5 | k = 1 | 1, 4 | первая ошибка |
| 6 | 7 | k ≤ 2, wi = 0 | 1, 4 | первая ошибка |
| 7 | 4 | k ≤ 2 | 1, 4, 5, 6 | первая ошибка |
| 8 | 11 | n ≤ 100, wi = 0 | 1, 2 | первая ошибка |
| 9 | 4 | n ≤ 100 | 1, 2, 3, 8 | первая ошибка |
| 10 | 11 | n ≤ 2 000, wi = 0 | 1, 2, 8 | первая ошибка |
| 11 | 4 | n ≤ 2 000 | 1, 2, 3, 8, 9, 10 | первая ошибка |
| 12 | 20 | wi = 0 | 1, 2, 4, 6, 8, 10 | первая ошибка |
| 13 | 14 | 1 — 12 | первая ошибка |
Пояснение к примеру
Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна 0 и не показана.
Есть и другие подходящие решения, в которых модернизируется 4 канала.
Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|