URI Online Judge | 2965

Delação Premiada

Por Maratona de Programação 2019, SBC BR Brazil

Timelimit: 1

A polı́cia da Nlogônia está investigando a máfia local. Eles já conhecem todos os membros e a estrutura da organização: a máfia nlogoniana tem N membros no total, e cada um é identificado por um inteiro entre 1 e N , onde 1 é o ID do chefão. Além disso, todo membro é subordinado direto de um outro membro, exceto o chefão.

Mesmo após meses de investigação, a polı́cia ainda não tem informação suficiente para prender nenhum membro da máfia por nenhum crime. Por isso, resolveram pedir a ajuda de um vidente: dado um membro da máfia, o vidente pode magicamente adivinhar os crimes que ele cometeu, e a polı́cia pode então confirmá-los através de interrogatório.

Além disso, quando um mafioso nlogoniano é interrogado, ele não só admite os seus crimes, mas também delata os crimes de seu superior direto, em troca de uma pena mais leve. Se este já não tiver sido preso, a polı́cia pode interrogá-lo também, e ele vai então delatar o superior dele, e assim por diante, até chegarem no chefão.

Infelizmente, o vidente só tem energia suficiente para adivinhar os crimes de no máximo K mafiosos, e a polı́cia quer usar seus poderes cuidadosamente pra prender o máximo possı́vel de bandidos. Dado o valor de K e a estrutura completa da máfia, qual a quantidade máxima de mafiosos que a polı́cia consegue prender?

Entrada

A primeira linha contém dois inteiros, N e K, onde N é o número de membros da máfia e K é o número máximo de mafiosos cujos crimes o vidente pode adivinhar (3 ≤ N ≤ 105 , 1 ≤ K < N). A segunda linha contém N − 1 inteiros, onde o i-ésimo deles identifica o superior direto do mafioso de ID i + 1.

É garantido que todos os inteiros da segunda linha estão entre 1 e N, e que todos os membros da máfia são subordinados do chefão, direta ou indiretamente.

Saída

Seu programa deve produzir uma única linha com um inteiro representando o número máximo de mafiosos que a polı́cia pode prender.

Exemplos de Entrada Exemplos de Saída

8 2
1 1 2 3 4 4 6

7

10 3
1 1 2 2 3 3 4 4 5

8