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

Solution (Python):
n,k = map(int,input().split())
a = [0] + list(map(int,input().split()))

ans = 0
if(a[1] != 1):
    ans += 1

links_c = [set() for _ in range(n+1)]
for i,ai in enumerate(a[2:],2):
    links_c[ai].add(i)

depth = [-1] * (n+1)
depth[1] = 0
stack = [1]
ts = [(0,1)]
while(stack):
    next = []
    while(stack):
        i = stack.pop()
        for j in links_c[i]:
            depth[j] = depth[i] + 1
            ts.append((depth[j],j))
            next.append(j)
    stack = next[::]

while( ts[-1][0] > k ):
    di,i = ts.pop()
    if( depth[i] <= k ):
        continue

    for j in range(k-1):
        i = a[i]

    ans += 1
    links_c[a[i]].remove(i)
    stack = [i]
    while(stack):
        next = []
        while(stack):
            i = stack.pop()
            depth[i] = 1
            for j in links_c[i]:
                next.append(j)
        stack = next[::]

print(ans)

Solution (Python):
from heapq import heappop,heappush

n,k = map(int,input().split())
a = [0] + list(map(int,input().split()))

ans = 0
if(a[1] != 1):
    ans += 1

links_c = [set() for _ in range(n+1)]
for i,ai in enumerate(a[2:],2):
    links_c[ai].add(i)

depth = [-1] * (n+1)
depth[1] = 0
stack = [1]
hq = []
while(stack):
    next = []
    while(stack):
        i = stack.pop()
        for j in links_c[i]:
            depth[j] = depth[i] + 1
            heappush(hq, (depth[j]*-1,j))
            next.append(j)
    stack = next[::]

while( hq[0][0]*-1 > k ):
    di,i = heappop(hq)
    if( depth[i] <= k ):
        continue

    for j in range(k-1):
        i = a[i]

    ans += 1
    links_c[a[i]].remove(i)
    stack = [i]
    while(stack):
        next = []
        while(stack):
            i = stack.pop()
            depth[i] = 1
            for j in links_c[i]:
                next.append(j)
        stack = next[::]

print(ans)


'''
首都の自己ループを除くと、首都を根として、
子→親の有向木になっている。

・首都のテレポート先は首都でないとダメ
→　長さ2以上の閉路を作るとうまくいかない

・首都以外は、首都までの距離をk以下にできればよい

もっとも根からの距離が遠い頂点xをとる。
xが根からの距離k以下　→　終了してOK
xが根からの距離k以上
→　xからk-1個離れた親を首都につなぎなおす
　そして再度最も遠い頂点を探す、を繰り返す。

'''

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]
ans = 0
if a[0] != 0:
    ans += 1
    a[0] = 0








def dfs(v, par):
    global ans
    for w in g[v]:
        if w != par:
            dfs(w, v)
            if f[w]+1 == k and v != 0:
                ans += 1
                continue
            f[v] = max(f[v], f[w]+1)
    return ans








g = [[] for _ in range(n)]
indeg = [0]*n
for i in range(1, n):
    g[a[i]].append(i)
    indeg[i] += 1
q = deque([0])
TS = [0]
while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            TS.append(w)
            q.append(w)

f = [0]*n
for w in TS[::-1]:
    if f[w] + 1 == k and a[w] != 0:
        ans += 1
        continue
    f[a[w]] = max(f[a[w]], f[w]+1)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if A[0] != 1:
  ans += 1
C = [[] for _ in range(n+1)]
P = [-1]*(n+1)
for i, a in enumerate(A[1:], 2):
  C[a].append(i)
  P[i] = a
def dfs(v):
  global ans
  temp = 0
  for nv in C[v]:
    temp = max(temp, dfs(nv)+1)
  if v == 1:
    return
  if P[v] != 1 and temp == k-1:
    temp = -1
    ans += 1
  return temp
dfs(1)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


N, K = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
graph = [[] for _ in range(N)]
Par = [-1]*N
for i, a in enumerate(A):
    if i == 0:
        if a != 1:
            ans += 1
        continue
    Par[i] = a-1
    graph[a-1].append(i)

qs = []

stack = [0]
Depth = [-1]*N
Depth[0] = 0
while stack:
    p = stack.pop()
    for np in graph[p]:
        Depth[np] = Depth[p] + 1
        stack.append(np)
    qs.append((Depth[p], p))

qs.sort(reverse=True)
checked = [False]*N

for d, s in qs:
    if d <= K: break
    if checked[s]: continue

    for _ in range(K-1):
        s = Par[s]
    
    que = [s]
    checked[s] = True
    while que:
        qq = []
        for p in que:
            for np in graph[p]:
                if not checked[np]:
                    checked[np] = True
                    qq.append(np)
        que = qq
    
    ans += 1

print(ans)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    f = list(map(lambda x : int(x) - 1, input().split()))

    
    ans = 0 + (f[0] != 0)
    f[0] = -1

    
    E = [[] for _ in range(n)]
    indeg = [0] * n
    for i in range(1, n):
        E[f[i]].append(i)
        indeg[i] += 1

    
    stack = [0]
    order = []
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in E[v]:
            stack.append(nv)
    order.reverse()

    dp = [-1] * n
    for v in order:
        res = 0
        for nv in E[v]:
            res = max(res, (dp[nv] + 1) % k)
        dp[v] = res

    ans += dp.count(k - 1)
    if dp[0] == k - 1:
        ans -= 1
    for v in E[0]:
        if dp[v] == k - 1:
            ans -= 1
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,k = map(int,input().split())
a = [int(i)-1 for i in input().split()]
edg = [[] for i in range(n)]
for i in range(1,n):
  edg[a[i]].append(i)
ans = [0] * n
ans[0] = a[0] != 0
def dfs(now):
  res = 0
  for e in edg[now]:
    res = max(res, dfs(e)+1)
  if res == k - 1 and a[now] != 0:
    ans[now] = 1
    res = -1
  return res
      
dfs(0)
print(sum(ans))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(links, n, k, v, p):
    height_from_leaf = 0
    cut_count = 0
    for u in links[v]:
        if u == 0:
            continue
        hgt, cut = dfs(links, n, k, u, v)
        height_from_leaf = max(height_from_leaf, hgt)
        cut_count += cut
    height_from_leaf += 1
    if p != 0 and height_from_leaf == k:
        height_from_leaf = 0
        cut_count += 1
    return height_from_leaf, cut_count


n, k, *aaa = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
for i, a in enumerate(aaa):
    a -= 1
    links[a].add(i)
_, ans = dfs(links, n, k, 0, 0)
if aaa[0] != 1:
    ans += 1

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, k = LI()
A = LI()
ans = 0
if A[0] != 1:
    ans += 1

A[0] = 1
G = [[] for _ in range(n)]
for i in range(1, n):
    G[A[i] - 1] += [i]

def dfs(u):
    global ans
    d = 0
    for v in G[u]:
        d = max(d, dfs(v) + 1)
    if d == k - 1:
        ans += (A[u] != 1)
        return -1
    return d

dfs(0)
print(ans)

Solution (Python):
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):
            
            self.ide_ele = inf
            
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            
            for i in range(n):
                self.seg[i + self.num] = A[i]
                
            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])

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

            cur += now
        ans = min(ans,cur+k*x)

    print(ans)
    return

def examC():
    H, W = LI()
    A = [SI()for _ in range(H)]

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

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
def DFS(graph,root,parent):
  dist = [-1]*(n+1)
  dist[root] = 0
  stack = [root]
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        parent[y] = x
        dist[y] = dist[x]+1
        stack.append(y)
  return dist


class Doubling:
  def __init__(self,graph,root):
    self.root = root
    n = len(graph)-1
    self.ancestor_ls = [[0]*(n+1)]
    self.distance = DFS(graph,root,self.ancestor_ls[0])
    self.bitn = n.bit_length()
    for i in range(1,self.bitn+1):
      ancestor_ls_app = [0]*(n+1)
      for j in range(1,n+1):
        ancestor_ls_app[j] = self.ancestor_ls[i-1][self.ancestor_ls[i-1][j]]
      self.ancestor_ls.append(ancestor_ls_app)
  
  def dist(self):
    return self.distance
  
  def parent(self):
    return self.ancestor_ls[0]

  def ancestor(self,v,depth):
    if depth == 1:
      return self.ancestor_ls[0][v]
    if depth == 2:
      return self.ancestor_ls[1][v]
    if depth == 0:
      return v
    if n<depth:
      return self.root
    ret = v
    for i in range(self.bitn):
      if depth&1<<i:
        ret = self.ancestor_ls[i][ret]
    return ret

import sys
input = sys.stdin.readline
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  ans += 1
graph = [[] for i in range(n+1)]
for i in range(1,n):
  graph[a[i]].append(i+1)
  graph[i+1].append(a[i])
if k > n:
  print(ans)
  exit()
sol = Doubling(graph,1)
dist = sol.dist()
if k == 1:
  print(n-dist.count(1)-dist.count(0)+ans)
  exit()
dls = []
for i in range(1,n+1):
  dls.append((dist[i],i))
vis = [0]*(n+1)
dls.sort()
dlsq = deque(dls)
parent = sol.parent()
while True:
  d,x = dlsq.pop()
  if d <= k:
    break
  if vis[x] == 1:
    continue
  ans += 1
  anc = sol.ancestor(x,k-1)
  stack = deque([anc])
  while stack:
    v = stack.pop()
    vis[v] = 1
    for u in graph[v]:
      if parent[u] == v and vis[u] != 1:
        stack.append(u)
print(ans)

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(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)
inc = [0] * (N + 1)
for i in range(N):
  if i + 1 == a[i]: continue
  e[a[i]].add(i + 1)
  inc[a[i]] += 1

t = set()
def dfs(x):
  global res
  d = 0
  for y in e[x]:
    d = max(d, dfs(y) + 1)
  if d == K - 1:
    res += (a[x - 1] != 1)
    return -1
  return d
  

dfs(1)
print(res)

Solution (Python):




import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

n,k =  [int(i) for i in input().split()]
a   =  [int(i)-1 for i in input().split()]



def dfs(u):
    global cnt
    depth = 0 
    
    for v in edges[u]:
        depth = max(depth, (dfs(v)+1)%k) 
        
    
    if depth==k-1 and u!=0 and a[u] != 0:
        cnt += 1
        
    return depth


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)   

dfs(0)    
print(cnt)

Solution (Python):
from collections import deque

N,K = map(int,input().split())

a = list(map(int,input().split()))

for i in range(N):
    a[i] -= 1

ans = 0

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


dis = [float("-inf")] * N
lnum = [0] * N

for i in range(N):

    lnum[a[i]] += 1

q = deque([])

for i in range(N):

    if lnum[i] == 0:
        q.append(i)
        dis[i] = 0

while len(q) > 0:

    now = q.popleft()
    if a[now] == 0:
        continue
    elif dis[now] == K-1:
        ans += 1
        dis[now] = -1
    
    dis[a[now]] = max(dis[a[now]] , dis[now] + 1)
    lnum[a[now]] -= 1

    if lnum[a[now]] == 0:
        q.append(a[now])


print (ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


from collections import defaultdict
answer = 0

def getlist():
	return list(map(int, input().split()))

INF = float("inf")
class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()


def DFS(G, visit, W, Wlist, node, K):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, visit, W, Wlist, i, K)
			Wlist[node].append(W[i] + 1)

	val = 0
	for i in Wlist[node]:
		if i == K and node != 0:
			global answer
			answer += 1
		else:
			val = max(val, i)
	W[node] = val


def main():
	N, K = getlist()
	a = getlist()
	G = Graph()
	for i in range(1, N):
		G.add_edge(i, a[i] - 1)
		G.add_edge(a[i] - 1, i)
	ans = 0
	if a[0] != 1:
		ans += 1
	if K == 1:
		for i in range(1, N):
			if a[i] != 1:
				ans += 1
		print(ans)
		return

	
	W = [0] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	
	DFS(G, visit, W, Wlist, 0, K)
	print(ans + answer)


if __name__ == '__main__':
	main()

Solution (Python):
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-1,-1,-1):
    q += depth_to_v[d]

q

answer = 0
for x in q:
    if x == 0:
        break
    if x not in V:
        continue
    if depth[x] <= K:
        break
    answer += 1
    y=x
    for _ in range(K-1):
        y = parent[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)

Solution (Python):
N, K = map(int, input().split())

P = list(map(lambda x: int(x) - 1, input().split()))
ans = 0 if P[0] == 0 else 1
P[0] = 0
Edge = [[] for _ in range(N)]
for i in range(1, N):
    p = P[i]
    Edge[i].append(p)
    Edge[p].append(i)

used = set([0])
stack = [0]
dist = [0]*N
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in used:
            used.add(vf)
            stack.append(vf)
            dist[vf] = 1 + dist[vn]

L = sorted(list(range(N)), key = lambda x: dist[x])

seen = set()
for l in L[::-1]:
    if l in seen:
        continue
    if dist[l] > K:
        vs = l
        for _ in range(K-1):
            vs = P[vs]
        seen.add(vs)
        stack = [vs]
        while stack:
            vn = stack.pop()
            for vf in Edge[vn]:
                if vf not in seen and vf != P[vs]:
                    seen.add(vf)
                    stack.append(vf)
        
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
if a[0] != 1:
	ans += 1
child = [[] for _ in range(n)]
for i in range(1, n):
	child[a[i]-1].append(i)


def dfs(x):
	global ans
	M = 0
	for v in child[x]:
		M = max(M, (dfs(v)+1)%k)
	if M == k-1 and a[x] != 1 and x != 0:
		ans += 1
	return M

dfs(0)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N,K=map(int,input().split())
A=[int(i)-1 for i in input().split()]
ans=0
if A[0]!=0:
  ans+=1
  A[0]=0
Graph=[[] for i in range(N)]
for i,a in enumerate(A[1:]):
  Graph[a].append(i+1)

def dfs(x):
  global ans
  height=0
  for a in Graph[x]:
    height=max(height,dfs(a)+1)
  
  if height==K-1:
    if A[x]!=0:
      ans+=1
      return -1
  return height


dfs(0)
print(ans)

Solution (Python):
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())

Solution (Python):
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())

Solution (Python):


import sys
from collections import defaultdict

sys.setrecursionlimit(10**7)
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)

    
    global res
    res = 0 if A[0] == 0 else 1

    def DFS(v, par):
        global res
        h = 0
        for to in D[v]:
            
            
            h = max(h, DFS(to, v))

        
        if h == k - 1 and par != 0:
            res += 1
            h = -1
        
        return h + 1

    DFS(0, 0)

    return res


print(main())

Solution (Python):
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] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
for j,i in hukai:
  if j <= k:
    continue
  dfs2(i,0)
print(ans)

Solution (Python):
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(1,n):
  b[a[i]-1].append(i)
huka = 0
kyo = [float("inf")] * n
z =[[]for i in range(n)]
def dfs(x,y):
  kyo[x] = y
  z[y].append(x)
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
for i in range(n-1,k,-1):
  for j in z[i]:
    dfs2(j,0)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI_()
    r = 0
    if a[0] != 0:
        r += 1
    e = collections.defaultdict(set)
    for i in range(1,n):
        e[a[i]].add(i)

    def f(i, p):
        m = 0
        r = 0
        for c in e[i]:
            ct,cr = f(c, i)
            r += cr
            if ct > m:
                m = ct
        if (m == k-1 and p != 0) or (m == k and p == 0):
            r += 1
            m = -1
        return (m+1,r)

    for c in e[0]:
        m,t = f(c,0)
        r += t
    return r


print(main())

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(now, par):
    global ans
    h = 0
    for child in g[now]:
        if child == par: continue
        h = max(h, dfs(child, now) + 1)
    if h == k - 1 and par != 0:
        ans += 1
        h = -1
    return h

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
g = [[] for _ in xrange(n)]
ans = 0
if a[0] != 1:
    a[0] = 1
    ans += 1
for i in xrange(n):
    g[a[i] - 1].append(i)
dfs(0, 0)
print ans

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(now, par):
    h = 0
    global ans
    for child in g[now]:
        if child == par: continue
        h = max(h, dfs(child, now))
    if h == k - 1 and par != 0:
        ans += 1
        h = -1
    return h + 1

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
g = [[] for _ in xrange(n)]
ans = 0
if a[0] != 1:
    a[0] = 1
    ans += 1
for i in xrange(n):
    g[a[i] - 1].append(i)
dfs(0, 0)
print ans

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def solve(s):
    global ans
    h=0
    for i in ch[s]:
        h=max(h,solve(i)+1)
    if h==k-1 and a[s]!=0:
        ans+=1
        a[s]=0
        return -1
    return h

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
ans=0
ch=[[] for _ in xrange(n)]

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

for i in xrange(1,n):
    ch[a[i]].append(i)

solve(0)
print(ans)

Solution (Python):
import collections

N, K = [int(s) for s in raw_input().split(' ')]
dest = [int(s)-1 for s in raw_input().split(' ')]

ans = 0

if dest[0] != 0:
    dest[0] = 0
    ans += 1

if K >= N:
    print(ans)
    raise SystemExit

source = collections.defaultdict(list)
for v in range(1,N):
    source[dest[v]].append(v)


dist = [0]*N
dist[0] = 0
topo = []
queue = collections.deque()
queue.append(0)
while queue:
    u = queue.popleft()
    topo.append(u)
    for v in source[u]:
        dist[v] = dist[u]+1
        queue.append(v)






good = set()
for u in reversed(topo):
    if u in good:
        continue
    if dist[u] <= K:
        break
    ans += 1
    ancestor = u
    for _ in range(K-1):
        ancestor = dest[ancestor]
    
    desc = []
    good.add(ancestor)
    desc.append(ancestor)
    i = 0
    while i < len(desc):
        anc = desc[i]
        i += 1
        for v in source[anc]:
            if v not in good:
                good.add(v)
                desc.append(v)
print(ans)

Solution (Python):
from sys import stdin
from itertools import repeat
def main():
    n, k = map(int, stdin.readline().split())
    a = map(int, stdin.readline().split(), repeat(10, n))
    for i in xrange(n):
        a[i] -= 1
    ans = 0
    if a[0]:
        a[0] = 0
        ans += 1
    xt = [0] * n
    last = [None] * n
    for i in xrange(1, n):
        xt[i] = last[a[i]]
        last[a[i]] = i
    p = [0]
    push = p.append
    pop = p.pop
    d = [None] * n
    while p:
        x = pop()
        if d[x] is None:
            d[x] = -1
            push(x)
            j = last[x]
            while j is not None:
                push(j)
                j = xt[j]
	elif d[x] == -1:
            d[x] = 1
            j = last[x]
            while j is not None:
		if x and d[j] >= k:
                    ans += 1
                elif d[x] < d[j] + 1:
                    d[x] = d[j] + 1
                j = xt[j]
    print ans
main()

Solution (Python):
from sys import exit, setrecursionlimit
from itertools import product

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

def argmin(ll):
  ll = list(ll)
  return ll.index(min(ll))

setrecursionlimit(1000000)

(N, K) = reads()
parent = [x-1 for x in reads()]

result = 0
if parent[0] != 0:
  parent[0] = 0
  result += 1

children = [[] for _ in range(N)]
for i in range(1, N):
  children[parent[i]].append(i)

color = [0] * N

def walk(i):
  global result
  for x in children[i]:
    walk(x)
    if color[x] == 1 and parent[x] != 0:
      result += 1
  color[i] = min([K] + [color[x]-1 for x in children[i] if color[x] >= 2])

walk(0)

print(result)