/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点 : 800 点
問題文
高橋王国には N 個の町があります。 町は 1 から N まで番号が振られています。 町 1 は首都です。
それぞれの町にはテレポーターが 1 台ずつ設置されています。 町 i (1≤i≤N) のテレポーターの転送先は町 a_i (1≤a_i≤N) です。 どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着けることが保証されます。
高橋王は正の整数 K が好きです。 わがままな高橋王は、いくつかのテレポーターの転送先を変え、次の条件が成り立つようにしたいと思っています。
- どの町から出発しても、テレポーターをちょうど K 回使うと、最終的に首都にいる。
条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを求めてください。
制約
- 2≤N≤10^5
- 1≤a_i≤N
- どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着ける。
- 1≤K≤10^9
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 a_2 ... a_N
出力
条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを出力せよ。
入力例 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) と変えればよいです。
Score : 800 points
Problem Statement
There are N towns in Snuke Kingdom, conveniently numbered 1 through N. Town 1 is the capital.
Each town in the kingdom has a Teleporter, a facility that instantly transports a person to another place. The destination of the Teleporter of town i is town a_i (1≤a_i≤N). It is guaranteed that one can get to the capital from any town by using the Teleporters some number of times.
King Snuke loves the integer K. The selfish king wants to change the destination of the Teleporters so that the following holds:
- Starting from any town, one will be at the capital after using the Teleporters exactly K times in total.
Find the minimum number of the Teleporters whose destinations need to be changed in order to satisfy the king's desire.
Constraints
- 2≤N≤10^5
- 1≤a_i≤N
- One can get to the capital from any town by using the Teleporters some number of times.
- 1≤K≤10^9
Input
The input is given from Standard Input in the following format:
N K a_1 a_2 ... a_N
Output
Print the minimum number of the Teleporters whose destinations need to be changed in order to satisfy King Snuke's desire.
Sample Input 1
3 1 2 3 1
Sample Output 1
2
Change the destinations of the Teleporters to a = (1,1,1).
Sample Input 2
4 2 1 1 2 2
Sample Output 2
0
There is no need to change the destinations of the Teleporters, since the king's desire is already satisfied.
Sample Input 3
8 2 4 1 2 3 1 2 3 4
Sample Output 3
3
For example, change the destinations of the Teleporters to a = (1,1,2,1,1,2,2,4).