Problem: 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.

Submission attempts (in order):
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)

    global ans
    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))
        if parent != 0 and height > K - 1:
            height = -1
            ans += 1
        return height + 1
    DFS(0, 0)
    return ans

print(main())

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

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)

    global ans
    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))
        if parent != 0 and height >= K - 1:
            height = -1
            ans += 1
        return height + 1
    DFS(0, 0)
    return ans

print(main())

Verdicts: Wrong Answer

Runtime Error

Accepted