← 返回题目列表

AtCoder · agc004_d

D. 传送器

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有 N 斯努克王国的城镇,编号方便 1 通过 N。 镇 1 是首都。

王国中的每个城镇都有一个 传送器,一种可以立即将人传送到另一个地方的设施。 城镇传送器的目的地 i 是城镇 a_i (1≤a_i≤N)。 可以保证 人们可以通过使用传送器多次从任何城镇到达首都.

King Snuke 喜欢整数 K。 自私的国王想要改变传送器的目的地,以便满足以下条件:

  • 从任意城镇出发,准确使用传送器后将到达首都 总共 K 次。

求出为了满足国王的愿望而需要改变目的地的传送器的最小数量。

约束

  • 2≤N≤10^5
  • 1≤a_i≤N
  • 人们可以通过多次使用传送器从任何城镇到达首都。
  • 1≤K≤10^9

输入

输入由标准输入按以下格式给出:

N K
a_1 a_2 ... a_N

输出

打印为了满足 King Snuke 的愿望而需要更改目的地的传送器的最小数量。


示例输入 1

3 1
2 3 1

示例输出 1

2

将传送器的目的地更改为 a = (1,1,1).


示例输入 2

4 2
1 1 2 2

示例输出 2

0

没有必要改变传送器的目的地,因为国王的愿望已经得到满足。


示例输入 3

8 2
4 1 2 3 1 2 3 4

示例输出 3

3

例如,将传送器的目的地更改为 a = (1,1,2,1,1,2,2,4).