D. Побег с горной базы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того как Лэнс Стерлинг украдет чемодан с горной базы, ему предстоит вернуться в штаб. Самый безопасный способ это сделать — съехать на лыжах по горе и сесть в вертолёт, который заранее будет стоять на одной из плоских полян, расположенных на горе.

Всего на горе есть $$$n$$$ полян, которые пронумерованы от $$$1$$$ до $$$n$$$ в порядке уменьшения высоты. Поляна с номером $$$1$$$ находится выше всего, а на каждую другую поляну ведет тропа с ровно одной поляны, которая находится выше. Лэнс может скатываться на лыжах только по тропам и только с более высокой поляны на более низкую.

У Лэнса в распоряжении есть $$$k$$$ вертолетов. Он собирается расставить их на некоторых полянах. Лэнс еще не знает, на какой из полян он окажется сразу после побега. Поэтому, хочет расставить вертолеты таким образом, чтобы количество полян, с которых он может добраться до какого-нибудь вертолета, было максимально.

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

Входные данные

В первой строке даны два числа $$$n$$$ и $$$k$$$ — количество полян на горе и вертолётов в распоряжении у Лэнса ($$$1 \le k \le n \le 300\,000$$$).

В следующей строке даны $$$n - 1$$$ целых чисел $$$p_2, p_3, \dots p_n$$$. Число $$$p_i$$$ означает, что тропа, ведущая на поляну $$$i$$$, начинается на поляне $$$p_i$$$ ($$$1 \le p_i \lt i$$$).

Выходные данные

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

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

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

|c|c|}

Подзадача

БаллыОграничения Дополнительные ограничения Необх. подзадачи Информация о проверке
110$$$n \le 20$$$первая ошибка
220$$$n \le 300$$$1первая ошибка
310$$$n \le 2000$$$1первая ошибка
430$$$n \le 5000$$$1, 2, 3первая ошибка
530$$$n \le 300000$$$1, 2, 3, 4первая ошибка
Пример
Входные данные
7 2
1 2 3 2 5 1
Выходные данные
6