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

Solution code:
import sys
sys.setrecursionlimit(10000)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
t = input()
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

def dfs(i, p):
	global res, ok
	MAX, SUM = 0, 0
	if t[i] == "1":
		num[i] = 1
	for j in adj[i]:
		if j == p:
			continue
		dfs(j, i)
		MAX = max(MAX, cnt[j])
		SUM += cnt[j]
		num[i] += num[j]
	if MAX * 2 > SUM:
		if p < 0:
			ok = False
			return
		else:
			res += SUM - MAX
			cnt[i] = MAX * 2 - SUM
	else:
		res += SUM // 2
		cnt[i] = SUM % 2
		if p < 0 and cnt[i] > 0:
			ok = False
	cnt[i] += num[i]
	return

ans = 10**8
for i in range(n):
	num = [0 for _ in range(n)]
	cnt = [0 for _ in range(n)]
	res = 0
	ok = True
	dfs(i, -1)
	if ok:
		ans = min(ans, res)

print(ans if ans < 10**8 else -1)

Submission status: Wrong Answer

Solution code:
n = int(input())
sa = input()
g = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
ans = 10 ** 9
for i in range(n):
    d = [-1] * n
    d[i] = 0
    l = [0] * len(g[i])
    for idx, j in enumerate(g[i]):
        s = [j]
        d[j] = 1
        while s:
            p = s.pop()
            if sa[p] == '1':
                l[idx] += d[p]
            for node in g[p]:
                if d[node] == -1:
                    d[node] = d[p] + 1
                    s.append(node)
    s = sum(l)
    if max(l) * 2 <= s and s % 2 == 0:
        ans = min(ans, s // 2)
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc034/tasks/agc034_e

まず、可能かどうかの判定をしたい
木を白黒に塗り分ける。
最後に集める点をまずVとする。
1回の操作で、2つの駒は
●両方vに近づく　　　　　　　→距離和は2減る(同一パス上に無い場合)
●片方は近づき、片方は離れる →距離和は変化しない (同一パス上にある場合)
の2通りがある。
なので、距離和を0にするためには全ての頂点との距離の和が偶数の点のみがVになりうる

Vを決めたとすると、答えの最小は距離和//2
あるVに集めるのが可能か & 最小の操作回数を求めたい

最小回数は、Vからのパスの直線上に無い2点を選び続けること
操作2を行うことで可能なになる例を考えたい→どう状況が変化するか？
片方の点が戻ることが異なる点→他のパス上の点からすると選択回数の総和は変わらない…？
同一パス上の点からすると、これも変わらない
→操作1だけで達成可能？

後はdfsかなぁ
→それぞれの子にある選択回数の最大値と最小値を管理する？
→Vで選択回数0にできるならおｋ

最大は何も消さずに送り付ける場合なので特に難しくない
最小は…　とやるのはきつくないか…？

選べないのはパス上の2点→あるパス上の寄与が過半数にならなければ全て選べるのでは？
パスから分岐している部分を考えると、分岐以降は全てパスの値を減らすのに使える
が、統合以降はパスの値になる
→これでいけそうだぞ！？

実装はdfs
最大値が分かればよいので、maxで送っていけばよい

十分か…？
最後の状態では、全てのパス上の寄与は0→過半数のパスはない
過半数がない場合、最大のパスに含まれる点とそれ以外のパス(→必ず存在する…？)を選べば過半数にはならない
過半数ではないのでそれ以外のパスは必ず存在する
→最後の状態に絶対収束する

なぜWA?
→前の回答はある点の寄与が半分以下だったらおkにしてる
→それだと正解なケース
→一つの点の寄与は過半数だが、一つのパスからの寄与はそうではない→ありえん
→一つの点からの寄与は半分以下だが、一つのパスからは過半数→ありうる
→可能を不可能として出力している？…ありえなさそう
→プログラムのミス？(総合距離が小さい or 最大距離が大きい)

→不可能を可能として出していた模様??

=====答えを見た=====
面倒くさいと切り捨てた方針っぽい
確かにパス上の寄与は正しそうだけど絶対正しいと証明できてたわけではない…

→部分木内での操作を行ってから部分木間で操作を行えばよい
dfs(v,p) = vの部分木内での操作のうち、どこまで操作回数を減らせるか
偶奇は保存される。過半数を超えるのがなかった場合極限まで減らせる

"""

import sys
from sys import stdin
sys.setrecursionlimit(3000)

dic = {}
def dfs(v,p):
    if (v,p) in dic:
        return dic[(v,p)]
    clis = []
    dsum = 0
    vsum = int(S[v])
    tmpsum = 0

    for nex in lis[v]:
        if nex != p:
            tnm,tds,tvs = dfs(nex,v)
            vsum += tvs
            dsum += tds + tvs
            tmpsum += tds + tvs
            clis.append(tds+tvs)
    clis.sort()
    if len(clis) == 0:
        dic[(v,p)] = (0,dsum,vsum)
        return 0,dsum,vsum

    if clis[-1] * 2 > tmpsum:
        ret = clis[-1] - sum(clis[:-1])
    else:
        ret = tmpsum % 2
    dic[(v,p)] = (ret,dsum,vsum)
    return ret,dsum,vsum
    

N = int(stdin.readline())
S = stdin.readline()
S = S[:-1]

lis = [ [] for i in range(N) ]
for i in range(N-1):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")
for st in range(N):

    nmin,dsum,vsum = dfs(st,st)
    if nmin == 0 and dsum % 2 == 0:
        ans = min(ans,dsum//2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)



"""
import sys
from sys import stdin
sys.setrecursionlimit(3000)
dic = {}

def dfs(v,p):
    if (v,p) in dic:
        return dic[(v,p)]

    nmax = 0
    nsum = 0
    vsum = 0
    
    for nex in lis[v]:
        if nex != p:
            tnm,tns,tv = dfs(nex,v)
            nmax = max(nmax , tnm + tv)
            nsum += tns+tv
            vsum += tv
    vsum += int(S[v])
    dic[(v,p)] = (nmax,nsum,vsum)
    return dic[(v,p)]
            

N = int(stdin.readline())
S = stdin.readline()
S = S[:-1]

lis = [ [] for i in range(N) ]
for i in range(N-1):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")
for st in range(N):

    nmax,nsum,vsum = dfs(st,st)

    #print (st+1,nmax,nsum,vsum)
    if nsum % 2 == 0 and nmax*2 <= nsum:
        ans = min(ans , nsum//2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)
"""

Submission status: Wrong Answer

Solution code:

"""

https://atcoder.jp/contests/agc034/tasks/agc034_e

まず、可能かどうかの判定をしたい
木を白黒に塗り分ける。
最後に集める点をまずVとする。
1回の操作で、2つの駒は
●両方vに近づく　　　　　　　→距離和は2減る(同一パス上に無い場合)
●片方は近づき、片方は離れる →距離和は変化しない (同一パス上にある場合)
の2通りがある。
なので、距離和を0にするためには全ての頂点との距離の和が偶数の点のみがVになりうる

Vを決めたとすると、答えの最小は距離和//2
あるVに集めるのが可能か & 最小の操作回数を求めたい

最小回数は、Vからのパスの直線上に無い2点を選び続けること
操作2を行うことで可能なになる例を考えたい→どう状況が変化するか？
片方の点が戻ることが異なる点→他のパス上の点からすると選択回数の総和は変わらない…？
同一パス上の点からすると、これも変わらない
→操作1だけで達成可能？

後はdfsかなぁ
→それぞれの子にある選択回数の最大値と最小値を管理する？
→Vで選択回数0にできるならおｋ

最大は何も消さずに送り付ける場合なので特に難しくない
最小は…　とやるのはきつくないか…？

選べないのはパス上の2点→あるパス上の寄与が過半数にならなければ全て選べるのでは？
パスから分岐している部分を考えると、分岐以降は全てパスの値を減らすのに使える
が、統合以降はパスの値になる
→これでいけそうだぞ！？

実装はdfs
最大値が分かればよいので、maxで送っていけばよい

十分か…？
最後の状態では、全てのパス上の寄与は0→過半数のパスはない
過半数がない場合、最大のパスに含まれる点とそれ以外のパスを選べば過半数にはならない
過半数ではないのでそれ以外のパスは必ず存在する
→最後の状態に絶対収束する

"""

import sys
from sys import stdin
sys.setrecursionlimit(3000)
dic = {}

def dfs(v,p):
    if (v,p) in dic:
        return dic[(v,p)]
    nmax = 0
    nsum = 0
    vsum = 0
    for nex in lis[v]:
        if nex != p:
            tmax,tsum,tv = dfs(nex,v)
            nmax = max(nmax , tmax + tv)
            nsum += tsum
            vsum += tv
    
    if S[v] == "1":
        dic[(v,p)] = (nmax,nsum+vsum,vsum+1)
        return nmax,nsum+vsum,vsum+1
    else:
        dic[(v,p)] = (nmax,nsum+vsum,vsum)
        return nmax,nsum+vsum,vsum
            

N = int(stdin.readline())
S = stdin.readline()
S = S[:-1]

lis = [ [] for i in range(N) ]
for i in range(N-1):
    a,b = map(int,stdin.readline().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")
for st in range(N):

    nmax,nsum,vsum = dfs(st,st)
    #print (st+1,nmax,nsum,vsum)
    if nsum % 2 == 0 and nmax*2 <= nsum:
        ans = min(ans , nsum//2)

if ans == float("inf"):
    print (-1)
else:
    print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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)

depth=[0]*N
num=[0]*N
sd=[0]*N

a=10**18

for i in range(N):
    depth=[0]*N
    num=[0]*N
    sd=[0]*N
    parent=[0]*N

    que=deque([(i,-1)])
    ans=[i]
    while que:
        v,pv=que.popleft()
        for nv in edge[v]:
            if nv!=pv:
                depth[nv]=depth[v]+1
                parent[nv]=v
                que.append((nv,v))
                ans.append(nv)
    ans=ans[::-1]
    #print(ans)

    for v in ans:
        res=depth[v]*(S[v]=="1")
        n=int(S[v])
        for nv in edge[v]:
            if nv!=parent[v]:
                res+=sd[nv]
                n+=num[nv]
        sd[v],num[v]=res,n

    res=[0]*N

    for v in ans:
        hosei=depth[v]
        s=sd[v]-num[v]*hosei
        if s%2==0:
            check=0
            node=-1
            for nv in edge[v]:
                if nv!=parent[v]:
                    if sd[nv]-num[nv]*hosei>s//2:
                        check=sd[nv]-num[nv]*hosei
                        node=nv
            if not check:
                res[v]=s//2
            else:
                minus=res[node]
                if check-2*minus<=s-check:
                    res[v]=s//2
                else:
                    res[v]=s-check+minus
        else:
            check=0
            node=-1
            k=s//2
            for nv in edge[v]:
                if nv!=parent[v]:
                    if sd[nv]-num[nv]*hosei>k+1:
                        check=sd[nv]-num[nv]*hosei
                        node=nv
            if not check:
                res[v]=k
            else:
                minus=res[node]
                if check-2*minus<=s-check:
                    res[v]=k
                else:
                    res[v]=s-check+minus

    test=res[i]
    if 2*test==sd[v]:
        a=min(a,test)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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)

depth=[0]*N
num=[0]*N
sd=[0]*N

a=10**18

for i in range(N):
    depth=[0]*N
    num=[0]*N
    sd=[0]*N
    parent=[0]*N

    que=deque([(i,-1)])
    ans=[i]
    while que:
        v,pv=que.popleft()
        for nv in edge[v]:
            if nv!=pv:
                depth[nv]=depth[v]+1
                parent[nv]=v
                que.append((nv,v))
                ans.append(nv)
    ans=ans[::-1]
    #print(ans)

    for v in ans:
        res=depth[v]*(S[v]=="1")
        n=int(S[v])
        for nv in edge[v]:
            if nv!=parent[v]:
                res+=sd[nv]
                n+=num[nv]
        sd[v],num[v]=res,n

    res=[0]*N

    for v in ans:
        hosei=depth[v]
        s=sd[v]-num[v]*hosei
        if s%2==0:
            check=0
            node=-1
            for nv in edge[v]:
                if nv!=pv:
                    if sd[nv]-num[nv]*hosei>s//2:
                        check=sd[nv]-num[nv]*hosei
                        node=nv
            if not check:
                res[v]=s//2
            else:
                minus=res[node]
                if check-2*minus<=s-check:
                    res[v]=s//2
                else:
                    res[v]=s-check+minus
        else:
            check=0
            node=-1
            k=s//2
            for nv in edge[v]:
                if nv!=pv:
                    if sd[nv]-num[nv]*hosei>k+1:
                        check=sd[nv]-num[nv]*hosei
                        node=nv
            if not check:
                res[v]=k
            else:
                minus=res[node]
                if check-2*minus<=s-check:
                    res[v]=k
                else:
                    res[v]=s-check+minus

    test=res[i]
    if 2*test==sd[v]:
        a=min(a,test)

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

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**4)

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)

depth=[0]*N
def dfs(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            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
    dfs(i,-1)
    #print(i,depth)
    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: Wrong Answer

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

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])!=0:
      L=[]
      s=0
      cc=0
      for vc in C[v]:
        L.append(Ans[vc][1]+Ans[vc][2])
        s=s+Ans[vc][0]
        cc=cc+Ans[vc][2]
      ss=min(sum(L)-max(L),sum(L)//2)
      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: Wrong Answer

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(ans)

Submission status: Wrong Answer

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]:
      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(ans)

Submission status: Wrong Answer

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)]
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(n+1)]
  flg = [0 for i in range(n+1)]
  while stack:
    x = stack.pop()
    if s[x] == "1":
      table[group[x]] += dist[x]
      flg[group[x]] = 1
    for y in graph[x]:
      if group[y] == -1:
        if flg[group[x]]:
          group[y] = group[x]
        else:
          group[y] = cnt
          cnt += 1
        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(-1)
else:
  print(ans)

Submission status: Wrong Answer

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(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc034/tasks/agc034_e

木を偶奇で塗り分ける
最終的に偶奇を合わせなくてはいけない？

最後に集める頂点を決め打ちする？
→その駒を選択できる回数に限界が決まる
まず、その頂点からの駒の距離の総和は偶数である必要がある

また、過半数が1つの駒からの寄与の場合は集めるのは不可能になる
→逆に言えばそれ以外はすべて構成可能？
→っぽさそう(だとしたら低いdifなのも納得がいく…)
→距離の遠い点から近づけて行けば、実際に可能そうである

後は全探索でおわり！ O(N**2)
まてよ？親から見て、の条件が抜けてないか？
→親に集まったsumのうち、一つの子からの寄与が半分を超えていなればおｋ

"""
import sys
sys.setrecursionlimit(5000)

N = int(input())
S = input()

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

ans = float("inf")

def dfs(v,p,d):

    dsum = 0
    dmax = 0

    if S[v] == '1':
        dsum += d

    for nex in lis[v]:
        if nex != p:
            ds = dfs(nex,v,d+1)
            dsum += ds
            dmax = max(dmax,ds)

    if v == p and (dmax * 2 > dsum or dsum % 2 == 1):
        return float("inf")
    else:
        return dsum

for i in range(N):

    nds = dfs(i,i,0)
    ans = min(ans,nds//2)


if ans == float("inf"):
    print (-1)
else:
    print (ans)

Submission status: Wrong Answer

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

def parorder(Edge, p):
    N = len(Edge)
    dist = [None]*N
    dist[p] = 0
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            dist[vf] = 1+dist[vn]
            ast(vf)
    return par, order, dist

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
S = list(map(int, readline().strip()))
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

INF = 10**9+7
ans = INF
for root in range(N):
    P, L, dist = parorder(Edge, root)
    K = sum(dist[i] for i in range(N) if S[i])
    if K&1:
        continue
    if ans <= K//2:
        continue
    size = S[:]
    for l in L[:0:-1]:
        p = P[l]
        size[p] += size[l]
    candi = [[] for _ in range(N)]
    dp = [0]*N
    for l in L[:0:-1]:
        p = P[l]
        res = 0
        if candi[l]:
            cs = sum(candi[l])
            ms = max(candi[l])
            if 2*ms > cs:
                res = 2*ms - cs
            else:
                res = cs&1
        candi[p].append(res+size[l])
    res = 0
    if candi[root]:
        cs = sum(candi[root])
        ms = max(candi[root])
        if 2*ms > cs:
            res = 2*ms - cs
        else:
            res = cs&1
    
    if res:
        continue
    else:
        ans = K//2
    
if ans == INF:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def f(v, vs):
    kminmax = rkoma = fff = ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax, ffmx = k1, ff
        rkoma += koma
        fff += ff
    r1 = kminmax+ffmx-fff if kminmax > fff - ffmx else fff % 2
    rkoma += km[v]
    return r1+rkoma, rkoma, fff+rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
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, c, fff = f(i+1, {i+1})
    if a == c:
        r = (fff-c)//2
print(r)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def f(v, vs):
    kminmax = 0
    r = 0
    rkoma = 0
    fff = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        kminmax = max(kminmax, k1)
        rkoma += koma
        fff += ff
    if 2*kminmax > fff:
        r1 = 2*kminmax-fff
    else:
        r1 = fff % 2
    rkoma += km[v]
    #print(v, r1 + rkoma, r + r2, rkoma)
    return r1 + rkoma, rkoma, fff + rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
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 = 10**10
for i in range(N):
    a, c, fff = f(i+1, {i+1})
    if a == c:
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def g(l, kms):
    if not l:
        return 0, 0
    m,s = max(l), sum(l)
    s = 0
    for mn, mx in zip(l, kms):
        s += min(mx, m)
    if 2*m > s:
        return 2*m - s, (s-m)
    return s % 2, s//2

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

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
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 = 10**10
for i in range(N):
    a, b, c, fff = f(i+1, {i+1})
    if a == c:
#    if (fff-c)%2==0 and b*2 == (fff-c):
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
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
    fff = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, k2, koma, ff = f(u, vs)
        ks.append(k1)
        rkoma += koma
        r += k2
        fff += ff
    r1, r2 = g(ks)
    # r1 深さの和、r2 操作の回数
    rkoma += km[v]
#    print(v, r1 + rkoma, r + r2, rkoma)
    return r1 + rkoma, r + r2, rkoma, fff + rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
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 = 10**10
for i in range(N):
    a, b, c, fff = f(i+1, {i+1})
#    print(fff-c)
    if (fff-c)%2==0 and b*2 == (fff-c):
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
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
    fff = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, k2, koma, ff = f(u, vs)
        ks.append(k1)
        rkoma += koma
        r += k2
        fff += ff
    r1, r2 = g(ks)
    # r1 深さの和、r2 操作の回数
    rkoma += km[v]
#    print(v, r1 + rkoma, r + r2, rkoma)
    return r1 + rkoma, r + r2, rkoma, fff + rkoma

N = int(input())
km = [0] + [int(i) for i in str(input().strip())]
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 = 10**10
for i in range(N):
    a, b, c, fff = f(i+1, {i+1})
#    print(fff-c)
    if a == c and (fff-c)%2==0:
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
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 str(input().strip())]
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 = 10**10
for i in range(N):
    a, b, c = f(i+1, {i+1})
    if a == c:
        r = min(r, b)
print(r if r != 10**10 else -1)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
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 str(input().strip())]
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: Wrong Answer

Solution code:
from collections import deque
N = int(input())
*S, = map(int, 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)

que = deque()
res = INF = 10**18
for i in range(N):
    dist = [-1]*N
    dist[i] = 0
    A = []
    for v in G[i]:
        que.append(v)
        dist[v] = 1
        r = 0
        while que:
            v = que.popleft()
            d = dist[v]
            if S[v]:
                r += d
            for w in G[v]:
                if dist[w] != -1:
                    continue
                dist[w] = d+1
                que.append(w)
        A.append(r)
    A.sort()
    s = sum(A)
    if s % 2 == 0 and 2*A[-1] <= s:
        res = min(res, sum(A)//2)
print(res)