Problem p04008 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
sys.setrecursionlimimt(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)

Buggy submission (verdict: Runtime Error):
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)
#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)