Problem p03021 (python)

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
leaf = set()
for i in range(1,n+1):
  if deg[i] == 1:
    leaf.add(i)
if s.count("1") == 1:
  print(0)
  exit()
ans = 10**18
for root in range(1,n+1):
  degr = deg[:]
  degr[root] += 1
  if root in leaf:
    continue
  stack = list(leaf)
  dpn = [[] for i in range(n+1)]
  dpmn = [[] for i in range(n+1)]
  dpmx = [[] for i in range(n+1)]
  info = [[0,0,0] for i in range(n+1)]
  for i in leaf:
    if s[i] == "1":
      info[i][0] += 1
  vis = set(i for i in leaf)
  anstmp = 0
  while stack:
    x = stack.pop()
    if dpn[x]:
      if len(dpn[x]) == 1:
        num = dpn[x][0]
        info[x] = [num,dpmn[x][0]+num,dpmx[x][0]+num]
        if s[x] == "1":
          info[x][0] += 1
      else:
        info[x][0] = sum(dpn[x])
        info[x][2] = sum(dpmx[x])+info[x][0]
        mxv = -1
        mxind = -1
        for i in range(len(dpmn[x])):
          if mxv < dpmn[x][i]+dpn[x][i]:
            mxv = dpmn[x][i]+dpn[x][i]
            mxind = i
        cnst = mxv-info[x][2]+dpmx[x][mxind]+dpn[x][mxind]
        info[x][1] = max(0,cnst%2,cnst)
        if s[x] == "1":
          info[x][0] += 1
    for y in graph[x]:
      if y not in vis:
        dpn[y].append(info[x][0])
        dpmn[y].append(info[x][1])
        dpmx[y].append(info[x][2])
        degr[y] -= 1
        if degr[y] == 1:
          vis.add(y)
          stack.append(y)
  if info[root][1] == 0:
    ans = min(ans,info[root][2]//2)
if ans == 10**18:
  print(-1)
else:
  print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
leaf = set()
for i in range(1,n+1):
  if deg[i] == 1:
    leaf.add(i)
if s.count("1") == 1:
  print(0)
  exit()
ans = 10**18
for root in range(1,n+1):
  degr = deg[:]
  degr[root] += 1
  if root in leaf:
    continue
  stack = list(leaf)
  dpn = [[] for i in range(n+1)]
  dpmn = [[] for i in range(n+1)]
  dpmx = [[] for i in range(n+1)]
  info = [[0,0,0] for i in range(n+1)]
  for i in leaf:
    if s[i] == "1":
      info[i][0] += 1
  vis = set(i for i in leaf)
  anstmp = 0
  while stack:
    x = stack.pop()
    if dpn[x]:
      if len(dpn[x]) == 1:
        num = dpn[x][0]
        info[x] = [num,dpmn[x][0]+num,dpmx[x][0]+num]
        if s[x] == "1":
          info[x][0] += 1
      else:
        info[x][0] = sum(dpn[x])
        info[x][2] = sum(dpmx[x])+info[x][0]
        mxv = -1
        mxind = -1
        for i in range(len(dpmn[x])):
          if mxv < dpmn[x][i]+dpn[x][i]:
            mxv = dpmn[x][i]+dpn[x][i]
            mxind = i
        cnst = mxv-info[x][2]+dpmx[x][mxind]+dpn[x][mxind]
        info[x][1] = max(0,cnst%2,cnst)
        if s[x] == "1":
          info[x][0] += 1
    for y in graph[x]:
      if y not in vis:
        dpn[y].append(info[x][0])
        dpmn[y].append(info[x][1])
        dpmx[y].append(info[x][2])
        degr[y] -= 1
        if degr[y] == 1:
          vis.add(y)
          stack.append(y)
  print(*info)
  if info[root][1] == 0:
    ans = 10**15
if ans == 10**18:
  print(-1)
else:
  print(2/0)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
leaf = set()
for i in range(1,n+1):
  if deg[i] == 1:
    leaf.add(i)
if s.count("1") == 1:
  print(0)
  exit()
ans = 10**18
for root in range(1,n+1):
  degr = deg[:]
  degr[root] += 1
  if root in leaf:
    continue
  stack = list(leaf)
  dpn = [[] for i in range(n+1)]
  dpmn = [[] for i in range(n+1)]
  dpmx = [[] for i in range(n+1)]
  info = [[0,0,0] for i in range(n+1)]
  for i in leaf:
    if s[i] == "1":
      info[i][0] += 1
  vis = set(i for i in leaf)
  anstmp = 0
  while stack:
    x = stack.pop()
    if dpn[x]:
      if len(dpn[x]) == 1:
        num = dpn[x][0]
        info[x] = [num,dpmn[x][0]+num,dpmx[x][0]+num]
        if s[x] == "1":
          info[x][0] += 1
        continue
      info[x][0] = sum(dpn[x])
      info[x][2] = sum(dpmx[x])+info[x][0]
      mxv = -1
      mxind = -1
      for i in range(len(dpmn[x])):
        if mxv < dpmn[x][i]+dpn[x][i]:
          mxv = dpmn[x][i]+dpn[x][i]
          mxind = i
      cnst = mxv-info[x][2]+dpmx[x][mxind]+dpn[x][mxind]
      info[x][1] = max(0,cnst%2,cnst)
      if s[x] == "1":
        info[x][0] += 1
    for y in graph[x]:
      if y not in vis:
        dpn[y].append(info[x][0])
        dpmn[y].append(info[x][1])
        dpmx[y].append(info[x][2])
        degr[y] -= 1
        if degr[y] == 1:
          vis.add(y)
          stack.append(y)
  if info[root][1] == 0:
    ans = 10**15
if ans == 10**18:
  print(-1)
else:
  print(2/0)

Buggy submission (verdict: Runtime Error):
n = int(input())
s = "Q"+input()
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
ans = 10**18
for root in range(1,n+1):
  stack = []
  group = [-1 for i in range(n+1)]
  dist = [0 for i in range(n+1)]
  group[root] = 0
  cnt = 1
  for y in graph[root]:
    stack.append(y)
    group[y] = cnt
    dist[y] = 1
    cnt += 1
  table = [0 for i in range(cnt)]
  while stack:
    x = stack.pop()
    if s[x] == "1":
      table[group[x]] += dist[x]
    for y in graph[x]:
      if group[y] == -1:
        group[y] = group[x]
        dist[y] = dist[x]+1
        stack.append(y)
  sm = sum(table)
  if sm%2 == 0 and max(table)*2 <= sm:
    ans = min(ans,sm//2)
if ans == 10**18:
  print(2/0)
  print(-1)
else:
  print(ans)