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 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
        push(j)
        while d[j] is None:
            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: Time Limit Exceeded

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] = max(f[v], f[w]+1)
    return ans


print(dfs(0, -1))

Submission status: Time Limit Exceeded

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(N):
    edge[a[i]].append(i)

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

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]:
        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: Time Limit Exceeded

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

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

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

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

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

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

Kparent=[-1 for i in range(N)]
for i in range(N):
    t=i
    for j in range(30):
        if (K-1)>>j &1==1:
            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]:
        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: Time Limit Exceeded

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

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

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

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

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

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

Kparent=[-1 for i in range(N)]
for i in range(N):
    t=i
    for j in range(30):
        if (K-1)>>j &1==1:
            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]:
        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: Time Limit Exceeded

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:
        stack.append(u)
print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)+ans)
  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: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
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)
for i in range(N):
  e[a[i]].add(i + 1)
#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)

eulbase = pow(10, 6)
euler = []
depth = [0] * (N + 1)
table = [0] * (N + 1)
def eulerdfs(x, d):
  global euler
  global depth
  global table
  table[x] = len(euler)
  depth[x] = d
  euler.append(d * eulbase + x)
  for y in e[x]:
    if x == y: continue
    eulerdfs(y, d + 1)
    euler.append(d * eulbase + x)

for i in range(len(euler) - 1, -1, -1): table[euler[i] % eulbase] = i
eulerdfs(1, 0)
#print(euler)
#print(table)
class minSegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res

class maxSegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
euler.pop()
minseg = minSegTree(len(euler), N * eulbase, euler)
maxseg = maxSegTree(len(euler), 0, euler)
#print(euler)
ex = dd(list)
for i in range(len(euler)):
  ok = i + 1
  ng = len(euler) + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if (maxseg.query(i, m) // eulbase) - (minseg.query(i, m) // eulbase) <= K: ok = m
    else: ng = m
  ex[i].append((ok, 1))
for i in range(len(euler), 0, -1):
  ex[i].append((i - 1, 0))
#print(ex)

import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]

dij = dijkstra(len(euler), ex)
print(dij.path(0, len(euler)) - 1 + res)

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict
answer = 0
#入力受け取り
def getlist():
	return list(map(int, input().split()))

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

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

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

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


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

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

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

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


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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(n):
  b[a[i]-1].append(i)
b[0].remove(0)
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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

import queue

N, K = map(int, input().split())
a = [0] + list(map(int, input().split()))

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

graph = [0]*(N+1)
for i in range(1, N+1):
	graph[i] = []

for i in range(2, N+1):
	graph[a[i]].append(i)


q = queue.Queue()
q.put((1, 0))

while not q.empty():
	(nowi, cnt) = q.get()
	# print(nowi, cnt)

	if cnt > K:
		ans += 1
		for e in graph[nowi]:
			q.put((e, 1+1))
	else:
		for e in graph[nowi]:
			q.put((e, cnt+1))

print(ans)

Submission status: Accepted

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

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

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

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

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

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

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

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

print(ans)


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

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

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

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

'''

Submission status: Accepted

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[a[w]], f[w]+1)

print(ans)

Submission status: Accepted

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]*(n+1)
for i, a in enumerate(A[1:], 2):
  C[a].append(i)
  P[i] = a
def dfs(v):
  global ans
  temp = 0
  for nv in C[v]:
    temp = max(temp, dfs(nv)+1)
  if v == 1:
    return
  if P[v] != 1 and temp == k-1:
    temp = -1
    ans += 1
  return temp
dfs(1)
print(ans)

Submission status: Accepted

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]
    checked[s] = True
    while que:
        qq = []
        for p in que:
            for np in graph[p]:
                if not checked[np]:
                    checked[np] = True
                    qq.append(np)
        que = qq
    
    ans += 1

print(ans)

Submission status: Accepted

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

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

    # we regard f as 0 rooted tree except for an edge 0 -> 0
    E = [[] for _ in range(n)]
    indeg = [0] * n
    for i in range(1, n):
        E[f[i]].append(i)
        indeg[i] += 1

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

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

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