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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

"""

"""

Submission status: Accepted

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

#親のリスト、頂点v、kが与えられたときに「vのk個上の祖先」を見る
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)

Submission status: Accepted

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

Submission status: Accepted

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)%k) #apply the maximum depth
        #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: Accepted

Solution code:
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 (dis)
print (ans)

Submission status: Accepted

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-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]
    # 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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#print(Graph)
def dfs(x):
  global ans
  height=0
  for a in Graph[x]:
    height=max(height,dfs(a)+1)
  #print(x,height,A[x])
  if height==K-1:
    if A[x]!=0:
      ans+=1
      return -1
  return height


dfs(0)
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
# coding:utf-8

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]:
            # 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: Accepted

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

Submission status: Accepted

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)

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


print(main())

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#print(topo)
#print({i:d for (i,d) in enumerate(dist)})
#print(repr(source))
#raise SystemExit

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]
    #print(ancestor)
    desc = []#collections.deque()
    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)

Submission status: Accepted

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:
		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: Accepted

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

Submission status: Runtime Error

Solution code:
import sys


def query(num):
    # output
    print("?", num)
    sys.stdout.flush()

    # input
    res = input()
    return res
  
ans = ""
while True:
    if len(ans) == 0:
        # 最上位桁のときは1からスタート
        min_lim = 1
    else:
        min_lim = 0

    for char in range(min_lim, 10):
        tmp = ans + str(char)
        res = query(tmp)
        if res == "N":
            ans += str(char - 1)
            break
    else:
        # 見ている桁が"9"、もしくは最後の桁、もしくは桁が存在しない
        for char in range(min_lim, 10)[::-1]:
            if query(ans + str(char) + "0") == "N":
                ans += str(char + 1)
                if ans[-1] != "9":
                    # 見ている桁が"9"でないときは必ず最後の桁
                    # 値が確定
                    print("!", ans)
                    exit()
                break
        else:
            # 最後の桁が"0"、もしくは桁が存在しない
            print(re)
            print("!", ans)
            exit()

Submission status: Runtime Error

Solution code:
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))
  if res == k - 1 and a[e] != 0 and e != 0:
    ans[e] = 1
    res = 1
  return res + 1
      
dfs(0)
print(sum(ans))

Submission status: Runtime Error

Solution code:
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(n):
  edg[a[i]].append(i)
ans = [0] * n
ans[0] = a[0] != 0
c = [1] * n
def dfs(now, rank):
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if rank == k:
        ans[e] = 1
        dfs(e, 1)
      else:
        dfs(e, time + 1)
dfs(0, 1)
print(sum(ans))

Submission status: Runtime Error

Solution code:
import sys
sys.recursionlimit(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(n):
  edg[a[i]].append(i)
ans = [0] * n
ans[0] = a[0] != 0
c = [1] * n
def dfs(now, time):
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if time == k:
        ans[e] = 1
        dfs(e, 1)
      else:
        dfs(e, time + 1)
dfs(0, 0)
print(sum(ans))

Submission status: Runtime Error

Solution code:
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(n):
  edg[a[i]].append(i)
ans = [0] * n
ans[0] = a[0] != 0
c = [1] * n
def dfs(now, time):
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if time == k:
        ans[e] = 1
        dfs(e, 1)
      else:
        dfs(e, time + 1)
dfs(0, 0)
print(sum(ans))

Submission status: Runtime Error

Solution code:
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(n):
  edg[a[i]].append(i)
ans = a[0] != 0
c = [1] * n
def dfs(now, time):
  global ans
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if time == k:
        ans += 1
        dfs(e, 1)
      else:
        dfs(e, time + 1)
dfs(0, 0)
print(int(ans))

Submission status: Runtime Error

Solution code:
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(n):
  edg[a[i]].append(i)
ans = a[0] != 0
c = [1] * n
def dfs(now, time):
  global ans
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if time == k:
        ans += 1
        dfs(e, 1)
      else:
        dfs(e, time + 1)
dfs(0, 0)
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(N)]
ans=int((a[0]!=0))
a[0]=0

depth=[-1 for i in range(N)]
depth[0]=0
def dfs(v):
    if depth[v]!=-1:
        return depth[v]
    depth[v]=dfs(a[v])+1
    return depth[v]

for i in range(1,N):
    depth[i]=dfs(i)
if K!=1:
    for i in range(N):
        if depth[i]%K==1 and depth[i]!=1:
            ans+=1
    print(ans)
else:
    for i in range(N):
        if depth[i]!=1 and depth[i]!=0:
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

const int SIZE = 100001;
priority_queue<pair<int, int>> D;//pair(depth, id)j
int P[SIZE];//parent, depth
vector<int> C[SIZE];//children
set<int> S;
void make_D(int id = 1, int depth = 0){
    D.push(make_pair(depth, id));
    for (int i = 0; i < C[id].size(); i++){
        make_D(C[id][i], depth + 1);
    }
}
void add_S(int x){
    S.insert(x);
    for (int i = 0; i < C[x].size(); i++){
        add_S(C[x][i]);
    }
}
int main(){
    int N, K; cin >> N >> K;
    int ans = 0;
    for (int i = 1; i <= N; i++){
        int ai; cin >> ai;
        C[ai].push_back(i);
        P[i] = ai;
    }
    if (P[1] != 1){
        C[P[1]].erase(C[P[1]].begin());
        P[1] = 1;
        ans++;
    }
    else
        C[1].erase(C[1].begin());
    
    make_D();
    while ((!D.empty()) && D.top().first > K)
    {
        pair<int, int> p = D.top();D.pop();
        if (S.find(p.second) == S.end()){
            cout << p.first << " " << p.second << endl;
            int x = p.second;
            for (int i = 1; i < K; i++){
                x = P[x];
            }
            add_S(x);
            ans++;
        }
    }
    cout << ans << endl;
}