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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
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, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 998244353


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

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


cnt = [-1] * n
cnt[0] = 0
q = [0]
while q:
    u = q.pop()
    for v in G[u]:
        if cnt[v] != -1:
            continue
        cnt[v] = cnt[u] + 1
        if cnt[v] == k + 1:
            cnt[v] = 0
            ans += 1
        q += [v]

print(ans)

Submission status: Wrong Answer

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


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


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


# TLE
# f = [0]*n
# print(dfs(0, -1))


# Topological Sort (TS)をDFSの代わりとする。
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[v], f[w]+1)

print(ans)

Submission status: Wrong Answer

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


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


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


# TLE
# f = [0]*n
# print(dfs(0, -1))


# Topological Sort (TS)をDFSの代わりとする。
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 = []
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[v], f[w]+1)

print(ans)

Submission status: Wrong Answer

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

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


f = [0]*n


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] = f[w]+1
    return ans


print(dfs(0, -1))

Submission status: Wrong Answer

Solution code:
from sys import stdin
input = stdin.readline
n, k = map(int, input().split())
aa = list(map(int, input().split()))
print(0)

Submission status: Wrong Answer

Solution code:
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 for _ in range(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 = 0
    ans += 1
  return temp
dfs(1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if A[0] != 1:
  ans += 1
T = [[] for _ in range(n+1)]
for i, a in enumerate(A[1:], 2):
  T[a].append(i)
dist = [-1]*(n+1)
dist[1] = 0
stack = [1]
if k == 1:
  while stack:
    v = stack.pop()
    d = dist[v]+1
    for nv in T[v]:
      if d > k:
        ans += 1
        dist[nv] = 1
      else:
        dist[nv] = d
      stack.append(nv)
else:
  while stack:
    v = stack.pop()
    d = dist[v]+1
    if d > k and T[v]:
      ans += 1
      d = 2
    for nv in T[v]:
      dist[nv] = d
      stack.append(nv)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if A[0] != 1:
  ans += 1
T = [[] for _ in range(n+1)]
for i, a in enumerate(A[1:], 2):
  T[a].append(i)
dist = [-1]*(n+1)
dist[1] = 0
stack = [1]
while stack:
  v = stack.pop()
  d = dist[v]+1
  for nv in T[v]:
    if d > k:
      ans += 1
      dist[nv] = 1
    else:
      dist[nv] = d
    stack.append(nv)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# import heapq as hp

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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)

q = []

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)
    if len(graph[p]) == 0:
        hp.heappush(q, (-Depth[p], p))

checked = [False]*N

while q:
    d, s = hp.heappop(q)
    d = -d
    if d <= K: break
    if checked[s]: continue
    
    
    for _ in range(K-1):
        s = Par[s]
    
    que = [s]
    while que:
        qq = []
        for p in que:
            for np in graph[p]:
                if not checked[np]:
                    checked[np] = True
                    qq.append(np)
        que = qq
    
    hp.heappush(q, (-Depth[Par[s]], Par[s]))
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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

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

stack = [0]
children = [1]*N
while stack:
    p = stack.pop()
    if p >= 0:
        stack.append(~p)
        for np in graph[p]:
            stack.append(np)
    else:
        p = ~p
        for ch in graph[p]:
            children[p] += children[ch]

q = [(-children[0], 0)]
Depth = [-1]*N
while q:
    _, s = hp.heappop(q)
    if s != 0: ans += 1
    Depth[s] = 0
    que = [s]
    for cycle in range(K+1):
        qq = []
        for p in que:
            for np in graph[p]:
                if Depth[np] == -1:
                    Depth[np] = Depth[p] + 1
                    qq.append(np)
        que = qq
        if not qq or (s != 0 and cycle == K-1):
            break
    if que:
        for p in que:
            hp.heappush(q, (-children[p], p))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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

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

stack = [0]
children = [1]*N
while stack:
    p = stack.pop()
    if p >= 0:
        stack.append(~p)
        for np in graph[p]:
            stack.append(np)
    else:
        p = ~p
        for ch in graph[p]:
            children[p] += children[ch]

q = [(-children[0], 0)]
Depth = [-1]*N
while q:
    _, s = hp.heappop(q)
    if s != 0: ans += 1
    Depth[s] = 0
    que = [s]
    for cycle in range(K+1):
        qq = []
        for p in que:
            for np in graph[p]:
                if Depth[np] == -1:
                    Depth[np] = Depth[p] + 1
                    qq.append(np)
        que = qq
        if not qq or (s != 0 and cycle == K):
            break
    if que:
        for p in que:
            hp.heappush(q, (-children[p], p))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hp

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

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

stack = [0]
children = [1]*N
while stack:
    p = stack.pop()
    if p >= 0:
        stack.append(~p)
        for np in graph[p]:
            stack.append(np)
    else:
        p = ~p
        for ch in graph[p]:
            children[p] += children[ch]

q = [(-children[0], 0)]
Depth = [-1]*N
while q:
    _, s = hp.heappop(q)
    if s != 0: ans += 1
    Depth[s] = 0
    que = [s]
    for _ in range(K):
        qq = []
        for p in que:
            for np in graph[p]:
                if Depth[np] == -1:
                    Depth[np] = Depth[p] + 1
                    qq.append(np)
        if not qq:
            break
        que = qq
    if que:
        for p in que:
            for np in graph[p]:
                hp.heappush(q, (-children[np], np))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n,k=map(int, input().split())
*a,=map(int, input().split( ))
if k>=n-1:
    print(1 if a[0]!=1 else 0)
    exit()

rev=[[] for _ in range(n+1)]

for i,ai in enumerate(a):
    rev[ai].append(i+1)

Q=deque()
Q.append((1,0))
cnt=0
ans=0 if a[0]==1 else 1
Done=[0]*(n+1)
Done[1]=1
Done[0]=1
while Q and cnt<=k:
    v,c=Q.popleft()
    Done[v]=1
    cnt=c
    for u in rev[v]:
        if not Done[u]:
            Q.append((u,c+1))
print(ans+n+1-sum(Done))

Submission status: Wrong Answer

Solution code:
from collections import deque

n,k=map(int, input().split())
*a,=map(int, input().split( ))
if k>=n-1:
    print(1 if a[0] else 0)
    exit()

rev=[[] for _ in range(n+1)]

for i,ai in enumerate(a):
    rev[ai].append(i+1)

Q=deque()
Q.append((1,0))
cnt=0
ans=0 if a[0]==1 else 1
Done=[0]*(n+1)
Done[1]=1
Done[0]=1
while Q and cnt<=k:
    v,c=Q.popleft()
    Done[v]=1
    cnt=c
    for u in rev[v]:
        if not Done[u]:
            Q.append((u,c+1))
print(ans+n+1-sum(Done))

Submission status: Wrong Answer

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 = 0
  return res
      
dfs(0)
print(sum(ans))

Submission status: Wrong Answer

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[now] != 0:
    ans[now] = 1
    res = 0
  return res + 1
      
dfs(0)
print(sum(ans))

Submission status: Wrong Answer

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[now] != 0 and now != 0:
    ans[now] = 1
    res = 0
  return res + 1
      
dfs(0)
print(sum(ans))

Submission status: Wrong Answer

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[now] != 0 and now != 0:
    ans[now] = 1
    res = 1
  return res + 1
      
dfs(0)
print(sum(ans))

Submission status: Wrong Answer

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
c = [1] * n
def dfs(now, rank):
  c[now] = 0
  for e in edg[now]:
    if c[e]:
      if rank == k + 1:
        ans[e] = 1
        dfs(e, 2)
      else:
        dfs(e, rank + 1)
dfs(0, 1)
print(sum(ans))

Submission status: Wrong Answer

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 + 1:
        ans[e] = 1
        dfs(e, 2)
      else:
        dfs(e, rank + 1)
dfs(0, 1)
print(sum(ans))

Submission status: Wrong Answer

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 + 1:
        ans[e] = 1
        dfs(e, 1)
      else:
        dfs(e, rank + 1)
dfs(0, 1)
print(sum(ans))

Submission status: Wrong Answer

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, rank + 1)
dfs(0, 1)
print(sum(ans))

Submission status: Wrong Answer

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

Solution code:
import sys,heapq

sys.setrecursionlimit(10**7)

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
if K>=N:
    print(ans)
    exit()

edge=[[] for i in range(N)]
for i in range(1,N):
    edge[a[i]].append(i)

depth=[-1 for i in range(N)]
def dep(v,val):
    depth[v]=val
    for nv in edge[v]:
        dep(nv,val+1)

dep(0,0)

dparent=[[-1 for i in range(17)] for i in range(N)]

for i in range(N):
    dparent[i][0]=a[i]

for i in range(1,17):
    for j in range(N):
        dparent[j][i]=dparent[dparent[j][i-1]][i-1]

bit=[i for i in range(17) if (K-1)>>i&1==1]
Kparent=[-1 for i in range(N)]
for i in range(N):
    t=i
    for j in bit:
        t=dparent[t][j]
    Kparent[i]=t

ok=[False]*N
for i in range(N):
    if K>=depth[i]:
        ok[i]=True

def dfs(v):
    ok[v]=True
    for nv in edge[v]:
        if not ok[nv]:
            dfs(nv)

que=[(-depth[i],i) for i in range(N)]
heapq.heapify(que)
while que:
    d,v=heapq.heappop(que)
    if not ok[v]:
        pv=Kparent[v]
        dfs(pv)
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,heapq

sys.setrecursionlimit(10**7)

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
if K>=N:
    print(ans)
    exit()

edge=[[] for i in range(N)]
for i in range(1,N):
    edge[a[i]].append(i)

depth=[-1 for i in range(N)]
def dep(v,val):
    depth[v]=val
    for nv in edge[v]:
        dep(nv,val+1)

dep(0,0)

dparent=[[-1 for i in range(17)] for i in range(N)]

for i in range(N):
    dparent[i][0]=a[i]

for i in range(1,17):
    for j in range(N):
        dparent[j][i]=dparent[dparent[j][i-1]][i-1]

bit=[i for i in range(17) if (K-1)>>i&1==1]
Kparent=[-1 for i in range(N)]
for i in range(N):
    t=i
    for j in bit:
        t=dparent[t][j]
    Kparent[i]=t

ok=set([])
for i in range(N):
    if K>=depth[i]:
        ok.add(i)

def dfs(v):
    ok.add(v)
    for nv in edge[v]:
        if nv not in ok:
            dfs(nv)

que=[(-depth[i],i) for i in range(N)]
heapq.heapify(que)
while que:
    d,v=heapq.heappop(que)
    if v not in ok:
        pv=Kparent[v]
        dfs(pv)
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

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

Solution code:
import sys
input = sys.stdin.readline

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

stack = []
dist = [-1]*n
stack.append(0)
dist[0] = 0
while stack:
  v = stack.pop()
  for nv in T[v]:
    if dist[nv] != -1:
      continue
    stack.append(nv)
    dist[nv] = dist[v] + 1
    if dist[nv] == k+1:
      if dist[v] != -2:
        ans += 1
        dist[v] = -2
      dist[nv] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

stack = []
dist = [-1]*n
stack.append(0)
dist[0] = 0
while stack:
  v = stack.pop()
  for nv in T[v]:
    if dist[nv] != -1:
      continue
    stack.append(nv)
    dist[nv] = dist[v] + 1
    if dist[nv] == k+1:
      ans += 1
      dist[nv] = 1
print(ans)

Submission status: Wrong Answer

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.parent_ls = [0]*(n+1)
    self.distance = DFS(graph,root,self.parent_ls)
    self.bitn = n.bit_length()
    self.ancestor_ls = [self.parent_ls]
    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.parent_ls

  def ancestor(self,v,depth):
    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 dls:
  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:
        stack.append(u)
print(ans)
"""

Submission status: Wrong Answer

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.parent_ls = [0]*(n+1)
    self.distance = DFS(graph,root,self.parent_ls)
    self.bitn = n.bit_length()
    self.ancestor_ls = [[0 for i in range(n+1)] for j in range(self.bitn+1)]
    self.ancestor_ls[0] = self.parent_ls
    for i in range(1,self.bitn+1):
      for j in range(1,n+1):
        self.ancestor_ls[i][j] = self.ancestor_ls[i-1][self.ancestor_ls[i-1][j]]
  
  def dist(self):
    return self.distance
  
  def parent(self):
    return self.parent_ls

  def ancestor(self,v,depth):
    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
  
  def LCA(self,u,v):
    if self.distance[u]<self.distance[v]:
      u,v = v,u
    dif = self.distance[u]-self.distance[v]
    w = self.ancestor(u,dif)
    if w == v:
      return v
    for i in range(self.bitn,-1,-1):
      if self.ancestor_ls[i][w] != self.ancestor_ls[i][v]:
        w,v = self.ancestor_ls[i][w],self.ancestor_ls[i][v]
    return self.ancestor_ls[0][v]

import sys
input = sys.stdin.readline
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()
parent = sol.parent()
"""
while dls:
  d,x = dls.pop()
  if d <= k:
    break
  if vis[x] == 1:
    continue
  ans += 1
  anc = sol.ancestor(x,k-1)
  stack = [anc]
  while stack:
    v = stack.pop()
    vis[v] = 1
    for u in graph[v]:
      if parent[u] == v:
        stack.append(u)
print(ans)
"""

Submission status: Wrong Answer

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.parent_ls = [0]*(n+1)
    self.distance = DFS(graph,root,self.parent_ls)
    self.bitn = n.bit_length()
    self.ancestor_ls = [[0 for i in range(n+1)] for j in range(self.bitn+1)]
    self.ancestor_ls[0] = self.parent_ls
    for i in range(1,self.bitn+1):
      for j in range(1,n+1):
        self.ancestor_ls[i][j] = self.ancestor_ls[i-1][self.ancestor_ls[i-1][j]]
  
  def dist(self):
    return self.distance
  
  def parent(self):
    return self.parent_ls

  def ancestor(self,v,depth):
    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
  
  def LCA(self,u,v):
    if self.distance[u]<self.distance[v]:
      u,v = v,u
    dif = self.distance[u]-self.distance[v]
    w = self.ancestor(u,dif)
    if w == v:
      return v
    for i in range(self.bitn,-1,-1):
      if self.ancestor_ls[i][w] != self.ancestor_ls[i][v]:
        w,v = self.ancestor_ls[i][w],self.ancestor_ls[i][v]
    return self.ancestor_ls[0][v]

from collections import Counter
import sys
import heapq as hq
input = sys.stdin.readline
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))
  exit()
dls = []
for i in range(1,n+1):
  dls.append((-dist[i],i))
vis = [0]*(n+1)
hq.heapify(dls)
parent = sol.parent()
while dls:
  d,x = hq.heappop(dls)
  if -d <= k:
    break
  if vis[x] == 1:
    continue
  ans += 1
  vis[x] = 1
  anc = sol.ancestor(x,k-1)
  stack = [anc]
  while stack:
    v = stack.pop()
    vis[v] = 1
    for u in graph[v]:
      if parent[u] == v:
        stack.append(u)
print(ans)

Submission status: Wrong Answer

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):
  e[i + 1].add(a[i])
  inc[a[i]] += 1

t = set()
def dfs(x, k):
  global t
  global res
  if x == 1: return False
  f = 0
  if k == K:
    f = 1
    k = 0
  for y in e[x]:
    if dfs(y, k + 1): t.add(x)
  if f: return True
  return False

for i in range(1, N + 1):
  if inc[i] == 0: dfs(i, 0)
print(len(t) + res)

Submission status: Wrong Answer

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):
  e[i + 1].add(a[i])
  inc[a[i]] += 1

t = set()
def dfs(x, k):
  global t
  global res
  if x == 1: return False
  f = 0
  if k == K:
    f = 1
  for y in e[x]:
    if dfs(y, k + 1): t.add(x)
  if f: return True
  return False

for i in range(1, N + 1):
  if inc[i] == 0: dfs(i, 0)
print(len(t) + 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()))
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 = max(0, (d[u] - 1) // K)
  t = []
  for v, _ in e[u]:
    y = max(0, (d[v] - 1) // K)
    if x != y:
      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)