import sys



sys.setrecursionlimit(10**4)



N=int(eval(input()))

S=eval(input())

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

for i in range(N-1):

    a,b=list(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)

from collections import deque



N=int(eval(input()))

S=eval(input())

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

for i in range(N-1):

    a,b=list(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)

import sys

sys.setrecursionlimit(10**4)
N = int(eval(input()))
S = eval(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = list(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)

from collections import deque

N = int(eval(input()))
S = eval(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
    a, b = list(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)

-import sys +from collections import deque -sys.setrecursionlimit(10**4) - - -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 +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() -                if sd[nv] - num[nv] * hosei > S // 2: -                    check = sd[nv] - num[nv] * hosei -                    node = nv -        if not check: -            return S // 2 +                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 -            minus = dfs2(node, v) -            if check - 2 * minus <= S - check: -                return S // 2 +            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 -                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: +                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(ans) +    print(a)