Problem:


Score : 1500 points

Problem Statement

You are given a tree with N vertices numbered 1, 2, ..., N. The i-th edge connects Vertex a_i and Vertex b_i.
You are also given a string S of length N consisting of 0 and 1. The i-th character of S represents the number of pieces placed on Vertex i.

Snuke will perform the following operation some number of times:

Choose two pieces the distance between which is at least 2, and bring these pieces closer to each other by 1. More formally, choose two vertices u and v, each with one or more pieces, and consider the shortest path between them. Here the path must contain at least two edges. Then, move one piece from u to its adjacent vertex on the path, and move one piece from v to its adjacent vertex on the path.

By repeating this operation, Snuke wants to have all the pieces on the same vertex. Is this possible?
If the answer is yes, also find the minimum number of operations required to achieve it.

Constraints

2 \leq N \leq 2000

|S| = N

S consists of 0 and 1, and contains at least one 1.

1 \leq a_i, b_i \leq N(a_i \neq b_i)

The edges (a_1, b_1), (a_2, b_2), ..., (a_{N - 1}, b_{N - 1}) forms a tree.

Input

Input is given from Standard Input in the following format:

N
S
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

Output

If it is impossible to have all the pieces on the same vertex, print -1. If it is possible, print the minimum number of operations required.

Sample Input 1

7
0010101
1 2
2 3
1 4
4 5
1 6
6 7

Sample Output 1

3

We can gather all the pieces in three operations as follows:

Choose the pieces on Vertex 3 and 5.

Choose the pieces on Vertex 2 and 7.

Choose the pieces on Vertex 4 and 6.

Sample Input 2

7
0010110
1 2
2 3
1 4
4 5
1 6
6 7

Sample Output 2

-1

Sample Input 3

2
01
1 2

Sample Output 3

0



Sample input:
7
0010101
1 2
2 3
1 4
4 5
1 6
6 7


Sample output:
3

Submission status: Runtime Error

Solution code:
n=int(input())
s=list(map(int,list(input())))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)

Submission status: Runtime Error

Solution code:
n=int(input())
s=list(map(int,list(input())))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(a):
  l,r,c,x=a[0]
  for u,v,d,y in a[1:]:l,r=max(max(l,u)-min(r,v),0)+((l^u)&1),r+v;c+=d;x+=y
  return [l,r,c,x]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
s=list(map(int,list(input())))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
def f(lrc):
  l1,r1,c1,x1=lrc[0]
  for l2,r2,c2,x2 in lrc[1:]:
    l1,r1=max(max(l1,l2)-min(r1,r2),0),r1+r2
    if r1%2!=l1%2:l1+=1
    c1+=c2
    x1+=x2
  return [l1,r1,c1,x1]
def dfs(root,node):
  lrcx=[]
  for mode in edge[node]:
    if root!=mode:
      lrcx.append(dfs(node,mode))
  if len(lrcx)==0:
    return [s[node]]*4
  l,r,c,x=f(lrcx)
  c+=s[node]
  return [l+c,r+c,c,x+c]
anss=[]
for i in range(n):
  l,r,c,x=dfs(-1,i)
  if l==c:
    anss.append(x-c)
if len(anss)==0:print(-1)
else:print(min(anss)//2)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

parent=[0]*N
depth=[0]*N
def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            parent[nv]=v
            dfs(nv,v)

def dfs2(v,pv):
    res=depth[v]*(S[v]=="1")
    for nv in edge[v]:
        if nv!=pv:
            res+=dfs2(nv,v)
    return res

ans=10**18

for i in range(N):
    depth[i]=0
    parent[i]=0
    dfs(i,-1)
    test=dfs2(i,-1)
    if test%2==0:
        for nv in edge[i]:
            check=dfs2(nv,i)
            if check>test//2:
                break
        else:
            ans=min(ans,test//2)

if ans==10**18:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
S=list(input())
G=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
ans=10**10
for i in range(n):#根
  D=deque([i])
  A=[i]
  V=[0]*n
  V[i]=1
  C=[[] for i in range(n)]
  while len(D)>0:
    x=D[0]
    D.popleft()
    for j in range(len(G[x])):
      if V[G[x][j]]==0:
        V[G[x][j]]=1
        D.append(G[x][j])
        A.append(G[x][j])
        C[x].append(G[x][j])
  A=A[::-1]
  Ans=[[0]*3 for i in range(n)]
  for v in A:
    if len(C[v])==1:
      vc=C[v][0]
      Ans[v]=[Ans[vc][0],Ans[vc][1]+Ans[vc][2],Ans[vc][2]]
    elif len(C[v])!=0:
      L=[]
      LL=[]
      cc=0
      s=0
      M=0
      for vc in C[v]:
        m=Ans[vc][1]+Ans[vc][2]
        if m>M:
          M=m
          MM=Ans[vc][0]
        L.append(Ans[vc][1]+Ans[vc][2])
        LL.append(2*Ans[vc][0]+Ans[vc][1]+Ans[vc][2])
        cc=cc+Ans[vc][2]
        s=s+Ans[vc][0]
      if sum(LL)-M-2*MM>=M:
        ss=sum(L)//2
      else:
        ss=sum(LL)-M-2*MM-s
      Ans[v]=[s+ss,sum(L)-2*ss,cc]
    if S[v]=="1":
      Ans[v][2]+=1
  if Ans[i][1]==0:
    if Ans[i][0]<ans:
      ans=Ans[i][0]
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
ushitapunichiakun

Submission status: Runtime Error

Solution code:

def g(l):
    if not l:
        return 0, 0
    m,s = max(l), sum(l)
    if 2*m > s:
        return 2*m - s, (s-m)
    return s % 2, s//2

def f(v, vs):
    ks = []
    r = 0
    rkoma = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, k2, koma = f(u, vs)
        ks.append(k1)
        rkoma += koma
        r += k2
    r1, r2 = g(ks)
    # r1 深さの和、r2 操作の回数
    rkoma += km[v]
#    print(v, r1 + rkoma, r + r2, rkoma)
    return r1 + rkoma, r + r2, rkoma

N = int(input())
km = [0] + [int(i) for i in input()]
d = [set() for _ in range(N+1)]

for _ in range(N-1):
    x, y = map(int, input().split())
    d[x].add(y)
    d[y].add(x)

r = -1
for i in range(N):
    a, b, c = f(i+1, {i+1})
    if a == c:
        r = b
print(r)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists, costs):
    stone = s[v]
    dist = 0
    cost = 0
    children_dists = []
    for u in links[v]:
        if u == p:
            continue
        us, ud, uc = first_dfs(u, v, stones, dists, costs)
        stone += us
        dist += us + ud
        cost += uc
        children_dists.append((us + ud, uc))
    # print(v, p, stone, dist, cost, children_dists)
    if len(children_dists) > 1:
        md, mc = max(children_dists)
        if dist - md < md - mc * 2:
            cost = dist - md + mc
        else:
            cost = dist // 2
        # print(v, p, md, hd, dist, cost)
    stones[v] = stone
    dists[v] = dist
    costs[v] = cost
    return stone, dist, cost


def second_dfs(v, p, pd, pc):
    children_dists = []
    dist = 0

    for u in links[v]:
        if u == p:
            dist += pd
            children_dists.append((pd, pc))
            continue
        ud = stones[u] + dists[u]
        uc = costs[u]
        dist += ud
        children_dists.append((ud, uc))
    # print(v, p, pd, pc, dist, children_dists)

    if len(children_dists) == 1:
        u = next(iter(links[v]))
        second_dfs(u, v, s[v], 0)
        return

    children_dists.sort(reverse=True)
    md1, mc1 = children_dists[0]
    md2, mc2 = children_dists[1]

    hd, m = divmod(dist, 2)
    # print(' ', hd, m, md1, mc1)
    if m == 0 and dist - md1 >= md1 - mc1 * 2:
        print(hd)
        exit()

    for u in links[v]:
        if u == p:
            continue
        us = stones[u]
        ud = dists[u]
        uc = costs[u]
        usd = us + ud
        if usd > 0:
            if usd == md1 and uc == mc1:
                md, mc = md2, mc2
            else:
                md, mc = md1, mc1
            td = dist - usd
            if td - md < md - mc * 2:
                vc = td - md + mc
            else:
                vc = td // 2
            second_dfs(u, v, td + (all_stones - us), vc)


n = int(input())
s = list(map(int, input()))
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
# print(links)
stones = [0] * n  # 1を根とした木の、頂点vの部分木以下（自身含む）にある石の数
dists = [0] * n  # 頂点vの部分木以下にある石 x それぞれのvとの距離 の和
costs = [0] * n  # 頂点v以下同士の石で、最大限頂点vに近づけておくためにできる操作の数
first_dfs(0, -1, stones, dists, costs)
# print(stones)
# print(dists)
# print(costs)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists, costs):
    stone = s[v]
    dist = 0
    cost = 0
    children_dists = []
    for u in links[v]:
        if u == p:
            continue
        us, ud, uc = first_dfs(u, v, stones, dists, costs)
        stone += us
        dist += us + ud
        cost += uc
        children_dists.append((us + ud, uc))
    # print(v, p, stone, dist, cost, children_dists)
    if len(children_dists) > 1:
        md, mc = max(children_dists)
        if dist - md < md - mc * 2:
            cost = dist - md + mc
        else:
            cost = dist // 2
        # print(v, p, md, hd, dist, cost)
    stones[v] = stone
    dists[v] = dist
    costs[v] = cost
    return stone, dist, cost


def second_dfs(v, p, pd, pc):
    children_dists = []
    dist = 0

    for u in links[v]:
        if u == p:
            dist += pd
            children_dists.append((pd, pc))
            continue
        ud = stones[u] + dists[u]
        uc = costs[u]
        dist += ud
        children_dists.append((ud, uc))
    # print(v, p, pd, pc, dist, children_dists)

    if len(children_dists) == 1:
        u = next(iter(links[v]))
        second_dfs(u, v, s[v], 0)
        return

    children_dists.sort(reverse=True)
    md1, mc1 = children_dists[0]
    md2, mc2 = children_dists[1]

    hd, m = divmod(dist, 2)
    # print(' ', hd, m, md1, mc1)
    if m == 0 and dist - md1 >= md1 - mc1 * 2:
        print(hd)
        exit()

    for u in links[v]:
        if u == p:
            continue
        us = stones[u]
        ud = dists[u]
        uc = costs[u]
        usd = us + ud
        if usd == md1 and uc == mc1:
            md, mc = md2, mc2
        else:
            md, mc = md1, mc1
        td = dist - usd
        if td - md < md - mc * 2:
            vc = td - md + mc
        else:
            vc = td // 2
        second_dfs(u, v, td + (all_stones - us), vc)


n = int(input())
s = list(map(int, input()))
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
# print(links)
stones = [0] * n  # 1を根とした木の、頂点vの部分木以下（自身含む）にある石の数
dists = [0] * n  # 頂点vの部分木以下にある石 x それぞれのvとの距離 の和
costs = [0] * n  # 頂点v以下同士の石で、最大限頂点vに近づけておくためにできる操作の数
first_dfs(0, -1, stones, dists, costs)
# print(stones)
# print(dists)
# print(costs)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
def solve(prev_pos, pos, times):
    if len(tree[pos]) == 1 and tree[pos][0] == prev_pos:
        return int(s[pos]) * times
    if prev_pos == -1:
        ans = []
        for i in tree[pos]:
            ans.append(solve(pos, i, times+1))
        return ans
    else:
        tmp_ans = int(s[pos]) * times
        for i in tree[pos]:
            if i != prev_pos:
                tmp_ans += solve(pos, i, times+1)
        return tmp_ans

ans = 10**10
for i in range(n):
    li = solve(-1, i, 0)
    sum_li, max_li = sum(li), max(li) 
    if sum_li % 2 == 0 and max_li*2 <= sum_li:
        ans = min(ans, sum_li // 2)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
cost = [[] for i in range(n)]
visited = [False]*n

dp = [0]*n
def solve(prev_pos, pos, times):
    if len(tree[pos]) == 1 and tree[pos][0] == prev_pos:
        return int(s[pos]) * times
    if prev_pos == -1:
        ans = []
        for i in tree[pos]:
            ans.append(solve(pos, i, times+1))
        return ans
    else:
        ans = int(s[pos]) * times
        for i in tree[pos]:
            if i != prev_pos:
                ans += solve(pos, i, times+1)
        return ans

ans = 1000000000000000
for i in range(n):
    li = solve(-1, i, 0)
    sum_li, max_li = sum(li), max(li) 
    if sum_li % 2 == 0 and max_li*2 <= sum_li:
        ans = min(ans, sum_li//2)
if ans == 1000000000000000:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
class LCA:
    def __init__(self,V,adj,root=0):
        self.adj=adj
        self.maxLog=18
        self.parent=[[-1]*V for _ in range(self.maxLog+1)]
        self.depth=[0]*V
        self.__dfs(-1,root,0)
        for i in range(self.maxLog):
            for j in range(V):
                if self.parent[i][j]!=-1:
                    self.parent[i+1][j]=self.parent[i][self.parent[i][j]]
    def __dfs(self,par,cur,dep):
        self.depth[cur]=dep
        self.parent[0][cur]=par
        for v in self.adj[cur]:
            if v==par:
                continue
            else:
                self.__dfs(cur,v,dep+1)
    def lca(self,a,b):
        if self.depth[a]>self.depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.depth[b]-self.depth[a])&(1<<i):
                b=self.parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.parent[i][a]!=self.parent[i][b]:
                a=self.parent[i][a]
                b=self.parent[i][b]
        return self.parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.depth[a]+self.depth[b]-2*self.depth[lca]

n=int(input())
s=input()
coins=s.count('1')
Adj=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(lambda i: int(i)-1,input().split())
    Adj[x].append(y)
    Adj[y].append(x)
lca=LCA(n,Adj)
root=-1
for i in range(1,n):
    if s[i]=='1':
        if root==-1:
            root=i
        else:
            root=lca.lca(root,i)
sumdist=0
maxdist=0
for i in range(n):
    if s[i]=='1':
        d=lca.dist(root,i)
        maxdist=max(maxdist,d)
        sumdist+=lca.dist(root,i)
#print(maxdist,sumdist)
if sumdist%2:
    if maxdist<=(sumdist//2):
        print(-1)
    else:
        d=2*maxdist-sumdist
        if not d%coins:
            cnt=sumdist-maxdist
            cnt+=(d//coins)*(coins-1)
            print(cnt)
        else:
            print(-1)
else:
    if maxdist<=(sumdist//2):
        print(sumdist//2)
    else:
        d=2*maxdist-sumdist
        if not d%coins:
            cnt=sumdist-maxdist
            cnt+=(d//coins)*(coins-1)
            print(cnt)
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
class LCA:
    def __init__(self,V,adj,root=0):
        self.adj=adj
        self.maxLog=18
        self.parent=[[-1]*V for _ in range(self.maxLog+1)]
        self.depth=[0]*V
        self.__dfs(-1,root,0)
        for i in range(self.maxLog):
            for j in range(V):
                if self.parent[i][j]!=-1:
                    self.parent[i+1][j]=self.parent[i][self.parent[i][j]]
    def __dfs(self,par,cur,dep):
        self.depth[cur]=dep
        self.parent[0][cur]=par
        for v in self.adj[cur]:
            if v==par:
                continue
            else:
                self.__dfs(cur,v,dep+1)
    def lca(self,a,b):
        if self.depth[a]>self.depth[b]:
            a,b=b,a
        for i in range(self.maxLog):
            if (self.depth[b]-self.depth[a])&(1<<i):
                b=self.parent[i][b]
        if a==b:
            return b
        for i in reversed(range(self.maxLog-1)):
            if self.parent[i][a]!=self.parent[i][b]:
                a=self.parent[i][a]
                b=self.parent[i][b]
        return self.parent[0][a]
    def dist(self,a,b):
        lca=self.lca(a,b)
        return self.depth[a]+self.depth[b]-2*self.depth[lca]

n=int(input())
s=input()
coins=s.count('1')
Adj=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(lambda i: int(i)-1,input().split())
    Adj[x].append(y)
    Adj[y].append(x)
lca=LCA(n,Adj)
root=-1
for i in range(1,n):
    if s[i]=='1':
        if root==-1:
            root=i
        else:
            root=lca.lca(root,i)
sumdist=0
maxdist=0
for i in range(n):
    if s[i]=='1':
        d=lca.dist(root,i)
        maxdist=max(maxdist,d)
        sumdist+=lca.dist(root,i)
print(maxdist,sumdist)
if sumdist%2:
    if maxdist<=(sumdist//2):
        print(-1)
    else:
        d=2*maxdist-sumdist
        if not d%coins:
            cnt=sumdist-maxdist
            cnt+=(d//coins)*(coins-1)
            print(cnt)
        else:
            print(-1)
else:
    if maxdist<=(sumdist//2):
        print(sumdist//2)
    else:
        d=2*maxdist-sumdist
        if not d%coins:
            cnt=sumdist-maxdist
            cnt+=(d//coins)*(coins-1)
            print(cnt)
        else:
            print(-1)