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: Wrong Answer

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, 0))
  e[i + 1].add((a[i], 0))
#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)
for u in range(1, N + 1):
  x = -(-d[u] // K)
  t = []
  for v, _ in e[u]:
    y = -(-d[v] // K)
    if x != y:
      if u == 1 or (v == 1): continue
      t.append((v, 0))
  for v, _ in t: e[u].discard((v, 0))
#print(e)
for i in range(1, N + 1):
  e[i].add((1, 1))
  e[1].add((i, 1))
#print(e)

import heapq

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res

pri = prim(N, e)
print(pri.MSTcost() + res)

Submission status: Wrong Answer

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()))
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, 0))
  e[i + 1].add((a[i], 0))
#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)

for u in range(1, N + 1):
  x = -(-d[u] // K)
  t = []
  for v, _ in e[u]:
    y = -(-d[v] // K)
    if x != y:
      if u == 1 or (v == 1): continue
      t.append((v, 0))
  for v, _ in t: e[u].discard((v, 0))
#print(e)
for i in range(1, N + 1):
  e[i].add((1, 1))
  e[1].add((i, 1))
#print(e)

import heapq

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res

pri = prim(N, e)
print(pri.MSTcost() + res)

Submission status: Wrong Answer

Solution code:
#d  tree
#code自体はあっている。ただ、そもそもアルゴリズムが違う。
#下から調べていかないと最適でない。
#Right Answer. 
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()]

#this is directed tree so every node is not reached yet
#return the depth from its lowest bottom
def dfs(u):
    global cnt
    depth = 0 #default, this value is used when bottom
    
    for v in edges[u]:
        depth = max(depth, dfs(v)+1) #apply the maximum depth
    if depth==k:
            depth = 0 #because the edge was alerady cut, by the following procedure
    
    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)

Submission status: Wrong Answer

Solution code:
#d  tree
#code自体はあっている。ただ、そもそもアルゴリズムが違う。
#下から調べていかないと最適でない。
#Right Answer. 
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()]

#this is directed tree so every node is not reached yet
#return the depth from its lowest bottom
def dfs(u):
    global cnt
    depth = 0 #default, this value is used when bottom
    
    for v in edges[u]:
        depth = max(depth, dfs(v)+1) #apply the maximum depth
    
    if depth>=k and u!=0:
        cnt += 1
        depth = 0
    
    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)

Submission status: Wrong Answer

Solution code:
#d  tree
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()]

#this is directed tree so every node is not reached yet
def dfs(u, d):
    change = 0
    if d>k:
        d = 0
        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: Wrong Answer

Solution code:
#d  tree
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()]

#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: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
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()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
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

	#BFS
	BF = BFS(G, 0, N)
	dist = BF.dist
	for i in range(1, N):
		if dist[i] % K == 1 and dist[i] > K:
			ans += 1
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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(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()
    if v not in s:
        continue
    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: Wrong Answer

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

for i in range(N):
    n = B.num
    d = B.search(n)
    if d<=K:
        break
    ans+=1
    B.add(d, -1)
    v = depth_to_index[d].pop()
    B.add(depth[v], -1)
    h = 1
    while h<K:
        pv = v
        v = a[v]
        h+=1
        que = deque([v])
        while que:
            vv = que.pop()
            for nv in G[vv]:
                if nv == pv:
                    continue
                que.append(nv)
                B.add(depth[nv], -1)
print(ans)

Submission status: Wrong Answer

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.discard(z)
        for w in desc_edge[z]:
            if w in V:
                qq.append(w)

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

Submission status: Wrong Answer

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]

Submission status: Wrong Answer

Solution code:
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)

leaf = [i for i in range(n) if not child[i]]
mods = [0 for _ in range(n)]

for i in range(len(leaf)):
	l = leaf[i]
	while a[l] != 1:
		mods[a[l]-1] = max(mods[a[l]-1], (mods[l]+1)%k)
		l = a[l]-1

for i in range(1, n):
	if mods[i] == k-1 and a[i] != 1:
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
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)

leaf = [i for i in range(n) if not child[i]]
mods = [0 for _ in range(n)]

for l in leaf:
	while a[l] != 1:
		mods[a[l]-1] = max(mods[a[l]-1], (mods[l]+1)%k)
		l = a[l]-1

for i in range(1, n):
	if mods[i] == k-1 and a[i] != 1:
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
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)

stack = [(0, 0)]
while stack:
	x, level = stack.pop()
	if level > k and (level-1) % k == 0:
		ans += 1
	for v in child[x]:
		stack.append((v, level+1))
print(ans)

Submission status: Wrong Answer

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)

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))

edges = [[] for i in range(n)]
dist = [0 for i in range(n)]
for i in range(n):
    edges[a[i]-1].append(i)


#print(edges)

def dfs(v):
    d= [0] * n
    q=[v]
    visited = [0] * n
    while q:
        v=q.pop()
        visited[v] = 1
        visited.append(v)
        for i in edges[v]:
            if not visited[i]:
                d[i] = d[v] + 1
                q.append(i)
    return d

dist = dfs(0)
ans = 0

for i in range(n):
    if (dist[i]-1)%k == 0 and dist[i]-1>0:
        ans += (dist[i]-1)//k

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

Submission status: Wrong Answer

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(n - 1):
        D[A[i + 1]].append(i + 1)

    q = deque([(0, 0)])
    # 首都は必ず自己ループでなければならない
    res = 0 if A[0] == 0 else 1
    while q:
        v, dist = q.pop()
        if dist > k:
            # 距離がkを超えた場合はその頂点を首都につなぎ直す
            dist = 1
            res += 1
        for vv in D[v]:
            q.append((vv, dist + 1))

    return res


print(main())

Submission status: Wrong Answer

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

N,K = map(int,input().split())
A = list(map(lambda x:int(x)-1, input().split()))

R = [[] for i in range(N)]
for i,a in enumerate(A):
    if i:
        R[a].append(i)

ans = int(A[0] != 0)

def rec(v,d,rooted):
    global ans
    lim = K-1 + int(rooted)
    for to in R[v]:
        if d >= lim:
            ans += 1
            rec(to,0,False)
        else:
            rec(to,d+1,rooted)
rec(0,0,True)

print(ans)

Submission status: Wrong Answer

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

N,K = map(int,input().split())
A = list(map(lambda x:int(x)-1, input().split()))

R = [[] for i in range(N)]
for i,a in enumerate(A):
    if i:
        R[a].append(i)

ans = int(A[0] != 0)

def rec(v,d,rooted):
    global ans
    lim = K-1 + int(rooted)
    for to in R[v]:
        if d == lim:
            ans += 1
            rec(to,0,False)
        else:
            rec(to,d+1,rooted)
rec(0,0,True)

print(ans)

Submission status: Wrong Answer

Solution code:
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)

    m,t = f(0,-1)
    return r + t


print(main())

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

if K == 1:
    print(sum(map(lambda x: x != 1, a)))
else:
    ans = 0
    if a[0] != 1:
        ans += 1
        a[0] = 1
    graph = [[] for _ in range(N+1)]
    for i, elem in enumerate(a):
        graph[elem].append(i+1)

    # print(graph)
    used = [False] * (N + 1)
    def rec(v, prev_v, k):
        if used[v]:
            return 0
        used[v] = True

        ans = 0
        if k < 0:
            ans += abs(k)
            k = K-1
        for next_v in graph[v]:
            if next_v == prev_v:
                continue
            ans += rec(next_v, v, k-1)
        return ans
    ans += rec(1, -1, K)
    print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

if K == 1:
    print(sum(map(lambda x: x != 1, a)))
else:
    ans = 0
    if a[0] != 1:
        ans += 1
        a[0] = 1
    graph = [[] for _ in range(N+1)]
    for i, elem in enumerate(a):
        graph[elem].append(i+1)

    # print(graph)
    used = [False] * (N + 1)
    def rec(v, prev_v, k):
        if used[v]:
            return 0
        used[v] = True

        ans = 0
        if k < 0:
            k = K-1
            ans += 1
        for next_v in graph[v]:
            if next_v == prev_v:
                continue
            ans += rec(next_v, v, k-1)
        return ans
    ans += rec(1, -1, K)
    print(ans)

Submission status: Wrong Answer

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

def dfs(s):
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

def dfs1(s):
    global ans
    for i in ch[s]:
        if 1+memo[a[i]]>k:
            memo[a[i]]=1
            memo[i]=1+memo[a[i]]
            ans+=1
        else:
            memo[i]=1+memo[a[i]]
        dfs1(i)
    return

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
ans=0
ch=[[] for _ in xrange(n)]
for i in xrange(1,n):
    dfs(i)
    
if a[0]!=0:
    a[0]=0
    ans+=1

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

dfs1(0)
print(ans)

Submission status: Wrong Answer

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

def dfs(s):
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

def dfs1(s):
    global ans
    for i in ch[s]:
        if 1+memo[a[i]]>k:
            memo[i]=1
            ans+=1
        else:
            memo[i]=1+memo[a[i]]
        dfs1(i)
    return

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
ans=0
ch=[[] for _ in xrange(n)]
for i in xrange(1,n):
    dfs(i)
memo[0]=0
if a[0]!=0:
    a[0]=0
    ans+=1

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

dfs1(0)
print(ans)

Submission status: Wrong Answer

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

def dfs(s):
    if s==n:
        memo[0]+=dfs(a[0])+1
        return
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

def dfs1(s):
    global ans
    for i in ch[s]:
        if 1+memo[a[i]]>k:
            memo[i]=1
            ans+=1
        else:
            memo[i]=1+memo[a[i]]
        dfs1(i)
    return

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
ans=0
ch=[[] for _ in xrange(n)]
for i in xrange(1,n+1):
    dfs(i)
if a[0]!=0:
    a[0]=0
    memo[0]=0
    ans+=1

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

dfs1(0)
print(ans)

Submission status: Wrong Answer

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

def dfs(s):
    if s==n:
        memo[0]+=dfs(a[0])+1
        return
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

def dfs1(s):
    global ans
    for i in ch[s]:
        if 1+memo[a[i]]>k:
            memo[i]=1
            ans+=1
        dfs1(i)
    return

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
ans=0
ch=[[] for _ in xrange(n)]
for i in xrange(1,n+1):
    dfs(i)
if a[0]!=0:
    a[0]=0
    memo[0]=0
    ans+=1

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

dfs1(0)
print(ans)

Submission status: Wrong Answer

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

def dfs(s):
    if s==n:
        memo[0]+=dfs(a[0])+1
        return
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
for i in xrange(1,n+1):
    dfs(i)

ans=0
if memo[0]!=k:
    if a[0]!=0:
        a[0]=0
        ans+=1
        memo[0]=0
    for i in xrange(1,n):
        if 1+memo[a[i]]>k:
            memo[i]=1
            a[i]=0
            ans+=1
else:
    if k==1:
        memo[0]=0
        for i in xrange(1,n):
            if 1+memo[a[i]]>k:
                memo[i]=1
                a[i]=0
                ans+=1
    else:
        a[0]=0
        ans+=1
        memo[0]=0
        for i in xrange(1,n):
            if 1+memo[a[i]]>k:
                memo[i]=1
                a[i]=0
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(s):
    if s==n:
        memo[0]+=dfs(a[0])+1
        return
    if memo[s]!=0:
        return memo[s]
    if s==0:
        return 0
    memo[s]+=dfs(a[s])+1
    return memo[s]

n,k=map(int,raw_input().split())
a=map(lambda x:int(x)-1,raw_input().split())
memo=[0]*n
for i in xrange(1,n+1):
    dfs(i)

ans=0
if memo[0]!=k:
    if a[0]!=0:
        a[0]=0
        ans+=1
        memo[0]=0
    for i in xrange(1,n):
        if 1+memo[a[i]]>k:
            memo[i]=1
            a[i]=0
            ans+=1
else:
    if k==1:
        for i in xrange(1,n):
            if 1+memo[a[i]]>k:
                memo[i]=1
                a[i]=0
                ans+=1
    else:
        a[0]=0
        ans+=1
        memo[0]=0
        for i in xrange(1,n):
            if 1+memo[a[i]]>k:
                memo[i]=1
                a[i]=0
                ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
tree = [[] for _ in range(N)]
for i, a in enumerate(map(int, input().split())):
    tree[a-1].append(i)
if 0 in tree[0]:
    ans = 0
    tree[0].remove(0)
else:
    ans = 1
stack = [(node, 1) for node in tree[0]]
visited = set([0])
while len(stack)!=0:
    n, depth = stack.pop()
    visited.update([n])
    if depth > K:
        depth = 1
        ans += 1
    stack.extend([(node, depth+1) for node in tree[n] if not node in visited])
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))


# 首都をノードとする根付き木を構成する
vec = [[] for i in range(N)]

for i in range(N):
    # 首都を根とした木を構成するのでノードの向きは a[i] - 1 => i
    vec[a[i] - 1].append(i)

# ループをなくす
if a[0] != 1:
    ans = 1
    a[0] = 1
else:
    ans = 0
vec[0].remove(0)

# あるノードのparはこのノードを指しているノードである
# depth = K - 1のとき
# その次のノードがparを指すように変更して探索を続ける
# 各ノードは一度しか探索しない
def dfs(v, depth, par):
    count = 0
    if depth == K:
        depth, par = 0, 0
        count += len(vec[v])
        for s in vec[v]:
            count += dfs(s, depth, par)
    else:
        for s in vec[v]:
            count += dfs(s, depth + 1, v)
    return count

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

Submission status: Wrong Answer

Solution code:
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:
                print j, d[j]
		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()

Submission status: Wrong Answer

Solution code:
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
    d = [None] * n
    f = [0] * n
    ans = 0
    d[0] = 0
    if a[0]:
        a[0] = 0
        ans += 1
    p = []
    push = p.append
    for i in xrange(n):
        if d[i] is not None:
            continue
        j = i
        while d[j] is None:
            push(j)
            j = a[j]
            f[j] = 1
        c = d[j] + 1
	for x in reversed(p):
            d[x] = c
            c += 1
        del p[:]
    for i in xrange(n):
        if f[i]:
            continue
        if d[i] > k:
            ans += (d[i] - 1) / k
    print ans
main()

Submission status: Wrong Answer

Solution code:
class city:
    def __init__(self,i,ai):
        self.i=i
        self.parent=ai
        self.children=[]
        self.done=False
    def addchild(self,c):
        self.children.append(c)
        
def recurdone(b,i,k):

    if b[i].done:
        return
    b[i].done=True

    if k==0:
        return
    for j in b[i].children:
        recurdone(b,j,k-1)
def recurfix(b,i,k):
    if k==1:
        b[i].done=True

        recurdone(b,i,km-1)
        b[b[i].parent].children.remove(i)
        if len(b[b[i].parent].children)==0:
            ends.append(b[i].parent)
        return
    if b[i].done:
        recurdone(b,i,km)
        return
    else:
        b[i].done=True

        recurfix(b,b[i].parent,k-1)

    

line=input().split()
n=int(line[0])
global km
km=int(line[1])
a=input().split()
for i in range (n):
    a[i]=int(a[i])
b=[]
for i in range (n):
    b.append(city(i,a[i]-1))
for i in range(n):
    b[b[i].parent].addchild(i)
changes=0
if b[0].parent!=0:
    b[b[0].parent].children.remove(0)
    b[0].parent=0
    b[0].addchild(0)
    changes=1


recurdone(b,0,km)
global ends
ends=[]
other=[]
for i in range(n):
    if b[i].done:
        pass
    else:
        if len(b[i].children)==0:
            ends.append(i)
        else:
            other.append(i)
for city in ends:
    if b[city].done:
        pass
    else:

        changes+=1
        recurfix(b,city,km)
for city in other:
    if b[city].done:
        pass
    else:

        changes+=1
        recurdone(b,city.i,km-1)
print (changes)