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
input = sys.stdin.readline

N=int(input())
S=input().strip()
E=[list(map(int,input().split())) for i in range(N-1)]

ELIST=[[] for i in range(N+1)]

for a,b in E:
    ELIST[a].append(b)
    ELIST[b].append(a)

DIS=[[N+10]*(N+1) for i in range(N+1)]

from collections import deque

for i in range(1,N+1):
    Q=deque([[i,0]])
    DIS[i][i]=0

    while Q:
        x,s=Q.pop()

        for to in ELIST[x]:
            if DIS[i][to]>s+1:
                DIS[i][to]=s+1
                Q.append([to,s+1])
        
OL=[i+1 for i in range(N) if S[i]=="1"]

LENGTH=0
OLLEN=len(OL)

if OLLEN==1:
    print(0)
    sys.exit()

for i in range(OLLEN-1):
    for j in range(i+1,OLLEN):
        LENGTH+=DIS[OL[i]][OL[j]]

if LENGTH%(2*(OLLEN-1))==0:
    print(LENGTH//(2*(OLLEN-1)))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    s = S()
    aa = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    sa = []
    for i in range(n):
        if s[i] == '1':
            sa.append(i)

    if len(sa) <= 1:
        return 0

    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv in e[u]:
                if v[uv]:
                    continue
                vd = k + 1
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d

    r = inf
    dd = []
    for i in range(n):
        dd.append(search(i))

    for i in range(n):
        di = dd[i]
        l = collections.defaultdict(int)
        for si in sa:
            if si == i:
                continue
            for c in e[i]:
                if di[si] - 1 == dd[c][si]:
                    l[c] += di[si]
                    break
        ls = sum(l.values())
        if ls % 2 == 1:
            continue
        lm = max(l.values())
        if ls // 2 < lm:
            continue
        t = ls // 2
        if r > t:
            r = t

    if r == inf:
        return -1

    return r


print(main())

Submission status: Wrong Answer

Solution code:
print("wakaranai")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)
n=int(input())
s=list(map(int,list(input()[:-1])))
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: Time Limit Exceeded

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
num=[0]*N
sd=[0]*N
def dfs(v,pv):
    res=depth[v]*(S[v]=="1")
    n=int(S[v])
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)
            res+=sd[nv]
            n+=num[nv]
    sd[v]=res
    num[v]=n

def dfs2(v,pv):
    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:
            return S//2
        else:
            minus=dfs2(node,v)
            if check-2*minus<=S-check:
                return S//2
            else:
                return 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:
            return k
        else:
            minus=dfs2(node,v)
            if check-2*minus<=S-check:
                return k
            else:
                return S-check+minus


ans=10**18

for i in range(N):
    depth[i]=0
    dfs(i,-1)
    #print(i,depth)
    test=dfs2(i,-1)
    if test*2==sd[i]:
        ans=min(ans,test)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・部分木の中で操作を行った場合の、残りdepth和の最小値と最大値を持ってdp
・補助的にコマの個数も持つ
・最大値：ただのdepthの和
・最小値：一番負担の大きな木から他の部分木を引いていった場合だが…
・最小値＋最大値から全部の最大値の和を引く形で更新
"""

N = int(readline())
S = readline().rstrip()
m = map(int,read().split())
AB = zip(m,m)

INF = 10**18

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

def solve_rooted(root):
    parent = [0] * (N+1)
    ts = []
    stack = [root]
    while stack:
        x = stack.pop()
        ts.append(x)
        for y in graph[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
    max_dep = [0]*(N+1)
    min_dep = [0]*(N+1)
    cnt = [0] * (N+1)
    for i,x in enumerate(S,1):
        cnt[i]=x-ord('0')
    for v in ts[::-1]:
        p = parent[v]
        max_dep_sum = 0
        x = 0
        for c in graph[v]:
            if c==p:
                continue
            cnt[v] += cnt[c]
            d1 = max_dep[c]; d2 = min_dep[c]
            d1 += cnt[c]; d2 += cnt[c]
            max_dep_sum += d1
            if x<d1+d2:
                x=d1+d2
        max_dep[v] = max_dep_sum
        x -= max_dep_sum
        if x<0:
            x=max_dep_sum&1
        min_dep[v] = x
    if min_dep[root]:
        return INF
    return max_dep[root]//2

answer = min(solve_rooted(v) for v in range(1,N+1))
if answer == INF:
    answer = -1
print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(9**9);n=int(input());s=list(map(int,list(input())));e=[[]for _ in[0]*n]
for _ in[0]*(n-1):a,b=map(int,input().split());e[a-1].append(b-1);e[b-1].append(a-1)
def f(a):
  l,r,c=a[0]
  for u,v,d in a[1:]:l,r=max(max(l,u)-min(r,v),(l^u)&1),r+v;c+=d
  return[l,r,c]
def g(o,u):
  if(o!=u)&(len(e[u])==1):return[s[u]]*3
  l,r,c=f([g(u,v)for v in e[u]if o-v]);c+=s[u];return[l+c,r+c,c]
a=[r-c for l,r,c in[g(i,i)for i in range(n)]if l==c];print(min(a)//2if a else-1)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(9**9);n=int(input());s=list(map(int,list(input())));e=[[]for _ in[0]*n]
for _ in[0]*(n-1):a,b=map(int,input().split());e[a-1].append(b-1);e[b-1].append(a-1)
def f(a):
  l,r,c=a[0]
  for u,v,d in a[1:]:l,r=max(max(l,u)-min(r,v),(l^u)&1),r+v;c+=d
  return[l,r,c]
def dfs(o,u):
  if(o!=u)&(len(e[u])==1):return[s[u]]*3
  l,r,c=f([dfs(u,v)for v in e[u]if o-v]);c+=s[u];return[l+c,r+c,c]
a=[r-c for l,r,c in[dfs(i,i)for i in range(n)]if l==c];print(min(a)//2if a else-1)

Submission status: Accepted

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
            clis.append( (tnm+tvs , tds+tvs) )

    if len(clis) == 0:
        dic[(v,p)] = (dsum,dsum,vsum)
        return dsum,dsum,vsum

    ret = float("-inf")
    for i in range(len(clis)):
        ret = max(ret , clis[i][0] - dsum + clis[i][1] )
    if ret < 0:
        ret %= 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)

#print (dic)
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: Accepted

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=[-1]*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(depth)

    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]
    #print(i,test,sd[i],sd)
    if 2*test==sd[i]:
        a=min(a,test)

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

Submission status: Accepted

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
num=[0]*N
sd=[0]*N
def dfs(v,pv):
    res=depth[v]*(S[v]=="1")
    n=int(S[v])
    for nv in edge[v]:
        if nv!=pv:
            depth[nv]=depth[v]+1
            dfs(nv,v)
            res+=sd[nv]
            n+=num[nv]
    sd[v]=res
    num[v]=n

def dfs2(v,pv):
    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:
            return S//2
        else:
            minus=dfs2(node,v)
            if check-2*minus<=S-check:
                return S//2
            else:
                return 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:
            return k
        else:
            minus=dfs2(node,v)
            if check-2*minus<=S-check:
                return k
            else:
                return S-check+minus


ans=10**18

for i in range(N):
    depth[i]=0
    dfs(i,-1)
    #print(i,depth)
    test=dfs2(i,-1)
    if test*2==sd[i]:
        ans=min(ans,test)

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

Submission status: Accepted

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
AAA=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+MM
      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: Accepted

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)
  if info[root][1] == 0:
    ans = min(ans,info[root][2]//2)
if ans == 10**18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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[:]
    cr = []
    for l in L[:0:-1]:
        p = P[l]
        size[p] += size[l]
    
    dp = [0]*N
    for l in L[:0:-1]:
        p = P[l]
        dp[p] += size[l] + dp[l]
        if p == root:
            cr.append((size[l] + dp[l], l))
    
    if cr:
        cm = -1
        cs = 0
        midx = None
        for sz, idx in cr:
            if cm < sz:
                cm = sz
                midx = idx
            cs += sz
        if 2*cm > cs:
            candi = [[] for _ in range(N)]
            cnt = None
            for l in L[:0:-1]:
                p = P[l]
                res = 0
                if candi[l]:
                    cis = sum(candi[l])
                    cim = max(candi[l])
                    if 2*cim > cis:
                        res = 2*cim-cis
                    else:
                        res = 1&cis
                if l == midx:
                    cnt = res + size[l]
                    break
                candi[p].append(res+size[l])
            
            if cs-cm < cnt:
                continue
    ans = K//2
    
if ans == INF:
    ans = -1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

def f(v, vs):
    kminmax = 0
    r = 0
    rkoma = 0
    fff = 0
    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 = k1
            ffmx = ff
        kminmax = max(kminmax, k1)
        rkoma += koma
        fff += ff
    if kminmax > fff - ffmx:
        r1 = kminmax+ffmx-fff
    else:
        r1 = fff % 2
    rkoma += km[v]
#    print(v, r1 + rkoma, rkoma, fff + 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
#print(f(4, {4}))
for i in range(N):
    a, c, fff = f(i+1, {i+1})
#    print(i, a, c)
    if a == c:
        r = min(r, (fff-c)//2)
print(r if r != 10**10 else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2000)

N = int(input())
for K in range(12) :
    if 2 ** K >= N :
        break

S = input()

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

def dfs(parent, current, dp) :
    max_dp = 0
    for i in path[current] :
        if i == parent :
            continue
        dp_ = [0] * 3
        dfs(current, i, dp_)
        dp[0] += dp_[0]
        dp[1] += dp_[1]
        max_dp = max(max_dp, dp_[1]+dp_[2])
        
    if max_dp > dp[1] :
        dp[2] = max_dp - dp[1]
    else :
        dp[2] = dp[1] % 2
    
    if parent == -1 :
        return dp
        
    else :
        if S[current] == '1' :
            dp[0] += 1
            
        dp[1] += dp[0]
        dp[2] += dp[0]

ret = 10 ** 10

for root in range(N) :
    dp = dfs(-1, root, [0] * 3)
    if dp[2] == 0 :
        ret = min(ret, dp[1] // 2)
        
if ret == 10 ** 10 :
    print(-1)
else :
    print(ret)

Submission status: Accepted

Solution code:
import sys
from heapq import nlargest

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)

    # only when source and leaf node
    if len(children_dists) == 1:
        u = next(iter(links[v]))
        return second_dfs(u, v, s[v], 0)

    (md1, mc1), (md2, mc2) = nlargest(2, children_dists)
    ret = INF

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

    for u in links[v]:
        if u == p:
            continue
        us = stones[u]
        ud = dists[u]
        uc = costs[u]

        # dist=0 node cannot be a center
        if ud == 0:
            continue
        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
        result = second_dfs(u, v, td + (all_stones - us), vc)
        ret = min(ret, result)

    return ret


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()
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)
INF = 10 ** 10
ret = second_dfs(0, -1, 0, 0)
print(-1 if ret == INF else ret)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    s = S()
    aa = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    sa = []
    for i in range(n):
        if s[i] == '1':
            sa.append(i)

    if len(sa) <= 1:
        return 0

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]

        t = 0
        if s[i] == '1':
            t = 1

        h = []
        tk = 0
        tc = 0
        for c in e[i]:
            if c == p:
                continue
            r = f(c,i)
            if r[0] < 1:
                continue
            tc += r[0]
            tk += r[0] + r[1]
            h.append([r[0]+r[1],r[2]])

        if p == -1:
            return h

        mk = 0
        mv = 0
        for u,v in h:
            if mk < u:
                mk = u
                mv = v
        if mk > tk - mk:
            kk = tk - mk
            mk -= kk
            kk += min(mv//2,mk)
            m[k] = (tc+t,tk,kk*2)
        else:
            m[k] = (tc+t,tk,tk//2*2)

        return m[k]

    r = inf

    for i in range(n):
        t = f(i,-1)
        tk = 0
        mk = 0
        for u,v in t:
            tk += u
        if tk % 2 == 1:
            continue

        ff = 1
        for u,v in t:
            kk = u-v
            nk = tk - u
            if kk > nk:
                ff = 0
        # print(i,ff,tk,mk,t)
        if ff == 0:
            continue
        if tk // 2 < mk:
            continue
        v = tk // 2
        if r > v:
            r = v

    if r == inf:
        return -1

    return r


print(main())