Problem:


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).



Sample input:
3 1
2 3 1


Sample output:
2

Submission status: Runtime Error

Solution code:
def examA():
    A, B, C = LI()
    ans = min(A*B*(C%2),A*C*(B%2),B*C*(A%2))
    print(ans)
    return

def examB():
    class segment_():
        def __init__(self, A, n, segfunc):
            #####単位元######要設定0or1orinf
            self.ide_ele = inf
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, x = LI()
    A = LI()
    Seg_min = segment_(A, N, lambda a, b: min(a,b))
    ans = inf
    for k in range(N):
        cur = 0
        for j in range(N):
            if j-k>=0:
                now = Seg_min.query(j-k,j+1)
            else:
                now = min(Seg_min.query(0,j+1),Seg_min.query(N-(k-j),N))
#            print(now,k,j)
            cur += now
        ans = min(ans,cur+k*x)

    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    V = [[]for _ in range(N)]
    ans = 0
    if A[0]!=1:
        ans += 1
        A[0] = 1
    for i in range(1,N):
        V[A[i]-1].append(i)
    def dfs(p,s):
        depth = 0
        cnt = 0
        for i in V[s]:
            d,c = dfs(s,i)
            depth = max(depth,d)
            cnt += c
        depth += 1
        if depth==K and p!=0:
            depth = 0
            cnt += 1
        return depth,cnt
    _,cnt = dfs(0,0)
    ans += cnt
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimimt(10 ** 6)
N, K = map(int, input().split())
a = list(map(int, input().split()))
if K >= N - 1:
  print(int(a[0] != 1))
  exit(0)
res = 0
if a[0] != 1:
  a[0] = 1
  res += 1
e = dd(set)
for i in range(N):
  e[a[i]].add(i + 1)
#print(e)
Q = dq([1])
d = [float("inf")] * (N + 1)
d[1] = 0
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d[q] > d[p] + 1:
      d[q] = d[p] + 1
      Q.append(q)
#print(d)

eulbase = pow(10, 6)
euler = []
depth = [0] * (N + 1)
table = [0] * (N + 1)
def eulerdfs(x, d):
  global euler
  global depth
  global table
  table[x] = len(euler)
  depth[x] = d
  euler.append(d * eulbase + x)
  for y in e[x]:
    if x == y: continue
    eulerdfs(y, d + 1)
    euler.append(d * eulbase + x)

for i in range(len(euler) - 1, -1, -1): table[euler[i] % eulbase] = i
eulerdfs(1, 0)
#print(euler)
#print(table)
class minSegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

class maxSegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
euler.pop()
minseg = minSegTree(len(euler), N * eulbase, euler)
maxseg = maxSegTree(len(euler), 0, euler)
#print(euler)
ex = dd(list)
for i in range(len(euler)):
  ok = i + 1
  ng = len(euler) + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if (maxseg.query(i, m) // eulbase) - (minseg.query(i, m) // eulbase) <= K: ok = m
    else: ng = m
  ex[i].append((ok, 1))
for i in range(len(euler), 0, -1):
  ex[i].append((i - 1, 0))
#print(ex)

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]

dij = dijkstra(len(euler), ex)
print(dij.path(0, len(euler)) - 1 + res)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
if K >= N - 1:
  print(int(a[0] != 1))
  exit(0)
res = 0
if a[0] != 1:
  a[0] = 1
  res += 1
e = dd(set)
for i in range(N):
  e[a[i]].add(i + 1)
#print(e)
Q = dq([1])
d = [float("inf")] * (N + 1)
d[1] = 0
while len(Q):
  p = Q.popleft()
  for q in e[p]:
    if d[q] > d[p] + 1:
      d[q] = d[p] + 1
      Q.append(q)
#print(d)

eulbase = pow(10, 6)
euler = []
depth = [0] * (N + 1)
table = [0] * (N + 1)
def eulerdfs(x, d):
  global euler
  global depth
  global table
  table[x] = len(euler)
  depth[x] = d
  euler.append(d * eulbase + x)
  for y in e[x]:
    if x == y: continue
    eulerdfs(y, d + 1)
    euler.append(d * eulbase + x)

for i in range(len(euler) - 1, -1, -1): table[euler[i] % eulbase] = i
eulerdfs(1, 0)
#print(euler)
#print(table)
class minSegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

class maxSegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
euler.pop()
minseg = minSegTree(len(euler), N * eulbase, euler)
maxseg = maxSegTree(len(euler), 0, euler)
#print(euler)
ex = dd(list)
for i in range(len(euler)):
  ok = i + 1
  ng = len(euler) + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if (maxseg.query(i, m) // eulbase) - (minseg.query(i, m) // eulbase) <= K: ok = m
    else: ng = m
  ex[i].append((ok, 1))
for i in range(len(euler), 0, -1):
  ex[i].append((i - 1, 0))
#print(ex)

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]

dij = dijkstra(len(euler), ex)
print(dij.path(0, len(euler)) - 1 + res)

Submission status: Runtime Error

Solution code:
#d  tree
n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]

#this is directed tree so every node is not reached yet
def dfs(u, d):
    change = 0
    if d>k:
        d = 1
        change += 1
    for v in edges[u]:
        if u!=v:
            change += dfs(v, d+1)
    return change


cnt = 0
if a[0]!=0:
    a[0] = 0
    cnt += 1

edges = [[] for _ in range(n)]
for i in range(0,n):
    pa = a[i]
    edges[a[i]].append(i)   

cnt += dfs(0,0)    
print(cnt)

Submission status: Runtime Error

Solution code:
#d  tree
n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]

#this is directed tree so every node is not reached yet
def dfs(u, d):
    change = 0
    if d>k:
        d = 1
        change += 1
    for v in edges[u]:
        if u==v:
            continue
        change += dfs(v, d+1)
    return change


cnt = 0
if a[0]!=0:
    a[0] = 0
    cnt += 1

edges = [[] for _ in range(n)]
for i in range(0,n):
    pa = a[i]
    edges[a[i]].append(i)   

cnt += dfs(0,0)    
print(cnt)

Submission status: Runtime Error

Solution code:
#d  tree
n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]

#this is directed tree so every node is not reached yet
def dfs(u, d):
    change = 0
    if d>k:
        d = 1
        change += 1
    for v in edges[u]:
        change += dfs(v, d+1)
    return change


cnt = 0
if a[0]!=0:
    cnt += 1

edges = [[] for _ in range(n)]
for i in range(1,n):
    pa = a[i]
    edges[a[i]].append(i)   

cnt += dfs(0,0)    
print(cnt)

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, n):
        self.N = n
        self.n = 1<<n.bit_length()
        self.data = [0] * (self.n + 1)
        self.num = 0#要素の個数(multisetの代用として使う場合のみ)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i
        self.num+=x
    def search(self, value):
        if value<1:
            return 0
        if value >self.num:
            return self.N+1
        x,sx = 0,0#x:現在の位置, sx:1~xまでの和
        step = self.n#ステップ幅.2^i
        while step:
            y = x+step
            sy = sx+self.data[y]#今のステップ幅で試す
            if sy < value:#目標より小さければx,sxを更新
                x,sx = y,sy
            step >>= 1#ステップ幅を半分にする
        return x+1
    def show(self):
        res = []
        a = 0
        for i in range(1, self.N+1):
            b = self.sum(i)
            if b<a:
                print('error')
                return
            for _ in range(a, b):
                res.append(i)
                a = b
        print(res)
from collections import deque
N, K = map(int, input().split())
a = list(map(lambda x:int(x)-1, input().split()))
G = [[] for _ in range(N)]
for i in range(1, N):
    G[a[i]].append(i)
depth = [0]*N
que = deque([0])
depth_to_index = [[] for _ in range(N)]
depth_to_index[0].append(0)
B = BIT(N)
while que:
    v = que.pop()
    d = depth[v]
    for nv in G[v]:
        depth[nv] = d+1
        depth_to_index[d+1].append(nv)
        que.append(nv)
        B.add(d+1, 1)
if a[0] == 0:
    ans = 0
else:
    if K%(depth[a[0]]+1) == 0:
        ans = 0
    else:
        ans = 1
s = set(list(range(1, N)))
for i in range(N):
    n = B.num
    d = B.search(n)
    if d<=K:
        break
    ans+=1
    v = depth_to_index[d].pop()
    B.add(depth[v], -1)
    s.remove(v)
    h = 1
    while h<K:
        v = a[v]
        h+=1
        que = deque([v])
        while que:
            vv = que.pop()
            B.add(depth[vv], -1)
            s.remove(vv)
            for nv in G[vv]:
                if nv not in s:
                    continue
                que.append(nv)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N,K = map(int,readline().split())
A = [int(x)-1 for x in readline().split()]

desc_edge = [set() for _ in range(N)]
parent = [0] * N
for i,x in enumerate(A[1:],1):
    # 根から葉に向かう向きに辺を持つ
    desc_edge[x].add(i)
    parent[i]=x

depth = [None] * N
q = [0]
depth[0]=0
while q:
    x = q.pop()
    for y in desc_edge[x]:
        q.append(y)
        depth[y] = depth[x]+1

V = set(range(N))

q=[]
depth_to_v = [[] for _ in range(N)]
for v,x in enumerate(depth):
    depth_to_v[x].append(v)
for d in range(N):
    q += depth_to_v[d]

answer = 0
while q:
    x = q.pop()
    if x == 0:
        break
    if x not in V:
        continue
    if depth[x] <= K:
        break
    answer += 1
    for _ in range(K-1):
        y = parent[y]
    # yの転送先を0に変更する、yの部分木は捨てる
    qq = [y]
    while qq:
        z = qq.pop()
        V.remove(z)
        for w in desc_edge[z]:
            if w in V:
                qq.append(w)

if A[0] != 0:
    answer += 1
print(answer)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
L = list(map(int,input().split()))

l = [[] for i in range(N)]
ans = 0 if L[0] == 1 else 1
L[0] = 0

for i in range(1,len(L)):
  l[L[i] - 1].append(i)

def search(ind,a):
  global ans
  if a > M:
    ans += 1
    a = 0
  if len(l[ind]) == 0:
    return
  for i in l[ind]:
    search(i,a+1)

search(0,0)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict

def main():
    N, K = LI()
    A = LI_()
    edges = defaultdict(list)
    for i, a in enumerate(A[1:], 1):
        edges[a].append(i)

    ans = 0
    if A[0] != 0:
        ans += 1
    def DFS(v, parent):
        global ans
        height = 0
        for to in edges[v]:
            height = max(height, DFS(to, v) + 1)
        if parent != 0 and height > K - 1:
            height = 0
            ans += 1
        return height
    DFS(0, 0)
    return ans

print(main())

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys
from collections import defaultdict, deque


INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n, k = LI()
    A = LI_()

    D = defaultdict(list)
    for i in range(1, n):
        D[A[i]].append(i)

    q = deque([(0, 0)])
    # 首都は必ず自己ループでなければならない
    global res
    res = 0 if A[0] == 0 else 1

    def DFS(v, par):
        global res
        h = 0
        for to in D[v]:
            # print('dfs {} -> {}'.format(v+1, to+1))
            # h: 葉からの距離の最大値
            h = max(h, DFS(to, v))
            
        # 根が首都ではなく，高さがk - 1の場合は首都につなぎ直す
        if h == k - 1 and par != 0:
            res += 1
            h = -1
        # print('Finish {} <- {}'.format(par+1, v+1))
        return h + 1

    DFS(0, 0)

    return res


print(main())

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(n):
  b[a[i]-1].append(i)
b[0].remove(0)
huka = 0
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] == 0:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x],y+1)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort()
huka = []
for i in range(n):
  huka.append(hukai[i][1])
huka = huka[::-1]
for i in huka:
  dfs2(i,0)
print(ans)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(n):
  b[a[i]-1].append(i)
b[0].remove(0)
kyo = [float("inf")] * n
def dfs(x,y,z):
  if y>k and z == 0:
    y= 0
    z = 1
  if y > k-1 and z == 1:
    y = 0
  kyo[x] = y
  for i in b[x]:
    dfs(i,y+1,z)
dfs(0,0,0)
print(kyo.count(0)-1+ans)