God saves man, who save himself !
God saves man, who save himself !
PS: в бизнесс классе можно полетать у себя дома ))
Гусейн серьезно относится к карантину и многим вещам .Ему дома одному скучно и он хочет прогуляться ,но это рискованно ! У Гусейна есть информация ,что n мест в городе безопасно.У Гусейна есть полно медикаментов,масок ,спиртов и респираторов . Он хочет создать себе k тайников в этих n местах таким образом,чтобы количество безопасных мест ,с которых он может добраться до какого нибудь тайника , было максимально! Гусейн находится сейчас на данный момент в самом первом безопасном месте и у него есть информация о безопасных путях ,которые ведут в безопасные места . С каждого безопасного места под номером i ведет один безопасный путь в j-ое безопасное место (i<j) ,обратно не пойти.Гусейну интересно ,чему равно максимальное количество безопасных мест ,с которых можно будет добраться до тайника ,если расставить тайники оптимальным образом .
Входные данные
В первой строке даны два числа n и k – количество безопасных мест и количество тайников ,которые хочет создать Гусейн
( 1 <= k <= n <= 300000) . В следующей строке даны n-1 целых чисел p2
,p3
,....,pn
. Число pi
означает ,что безопасный путь ,ведущий в безопасное место i ,начинается в pi
-ом безопасном месте ( 1 <=pi
< i ).
Выходные данные
Выведите одно число – максимальное количество безопасных мест ,с которых можно будет добраться до тайника при оптимальной расстановке тайников .
7 2 1 2 3 2 5 1
6
2 2 1
2
5 2 1 1 3 2
5