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:
#n,m=map(int,input().split())
from collections import deque
n=int(input())
s='_'+input()
g=[[] for i in range(1+n)]
v=[0]*(1+n)
ans=[]

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

def bfs(x):
    r=0
    p=deque()
    p.append((x,1))
    while p:
        c,depth=p.popleft()
        if s[c]=='1':
            r+=depth
        v[c]=1
        for i in g[c]:
            if v[i]==0:
                p.append((i,depth+1))
    return r

for x in range(1,n+1):
    h=[]
    for nb in g[x]:
        v=[0]*(1+n)
        v[x]=1
        h.append(bfs(nb))
    d=sum(h)
    
    if d%2==0 and max(h)<=d//2:
        ans.append(d//2)
    #print(x,d,h,ans)
if ans:
    ans=min(ans)
else:
    ans=-1
print(ans)

Submission status: Wrong Answer

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]
        if ud > 0:
            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:
                hd = td - md + mc
            else:
                hd = td // 2
            second_dfs(u, v, td + (all_stones - us), hd)


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

Solution code:
import sys

sys.setrecursionlimit(10000)


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


def solve():
    all_stones = sum(s)
    if all_stones == 1:
        return 0
    for v in range(n):
        stone, dist, cost = dfs(v, -1)
        if dist == cost * 2:
            return cost
    return -1


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)
print(solve())

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


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


def solve():
    all_stones = sum(s)
    if all_stones == 1:
        return 0
    for v in range(n):
        stone, dist, cost = dfs(v, -1)
        if dist == cost * 2:
            return cost
    return -1


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)
print(solve())

Submission status: Wrong Answer

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)
        cost = dist // 2
        mdf = md - mc * 2
        if cost - mc < mdf:
            cost = dist - md + mc
        # 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)
    mdf = md1 - mc1 * 2
    # print(' ', hd, m, md1, mc1, mdf)
    if m == 0 and hd - mc1 >= mdf:
        print(hd)
        exit()

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


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# 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: Wrong Answer

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
        children_dists.append((us + ud, uc))
    # print(v, p, stone, dist, cost, children_dists)
    if len(children_dists) > 1:
        md, mc = max(children_dists)
        cost = dist // 2
        mdf = md - mc * 2
        if cost - mc < mdf:
            cost = dist - md + mc
        # 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)
    mdf = md1 - mc1 * 2
    # print(' ', hd, m, md1, mc1, mdf)
    if m == 0 and hd - mc1 >= mdf:
        print(hd)
        exit()

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


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# 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: Wrong Answer

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(ud)
    # print(v, p, stone, dist, cost, children_dists)
    if len(children_dists) > 1:
        md = max(children_dists)
        hd = dist // 2
        if hd < md:
            hd = dist - md
        dist -= hd * 2
        cost += hd
        # 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 = []
    cost = 0

    for u in links[v]:
        if u == p:
            children_dists.append(pd)
            cost += pc
            continue
        children_dists.append(stones[u] + dists[u])
        cost += costs[u]

    sd = sum(children_dists)
    hd, m = divmod(sd, 2)
    # print(v, p, sd, hd, m, children_dists, pd)
    if m == 0 and all(hd >= d for d in children_dists):
        print(cost + hd)
        exit()

    if len(children_dists) == 1:
        md1, md2 = children_dists[0], 0
    else:
        children_dists.sort(reverse=True)
        md1, md2 = children_dists[:2]

    for u in links[v]:
        if u == p:
            continue
        us = stones[u]
        ud = dists[u]
        uc = costs[u]
        if ud > 0:
            cd = us + ud
            cc = cost - uc
            md = md1 if cd != md1 else md2
            td = sd - cd
            hd = td // 2
            if hd < md:
                hd = td - md
            second_dfs(u, v, sd - cd - hd * 2 + (all_stones - us), hd + cc)


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
costs = [0] * n
first_dfs(0, -1, stones, dists, costs)
# print(stones)
# print(dists)
# print(costs)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10000)
n = int(input())
s = 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
flag = False
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:
        flag = True
        ans = min(ans, sum_li // 2)
if not flag:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10000)
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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, pd, ans):
    children_dists = []

    for u in links[v]:
        if u == p:
            children_dists.append(pd)
            continue
        children_dists.append(stones[u] + dists[u])

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, pd)
    if m == 0 and all(h >= d for d in children_dists):
        ans.append(h)

    for u in links[v]:
        if u == p:
            continue
        us = stones[u]
        ud = dists[u]
        if us > 0 and ud > 0:
            second_dfs(u, v, sd - us - dists[u] + (all_stones - us), ans)


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
ans = []
second_dfs(0, -1, 0, ans)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, pd, ans):
    children_dists = []

    for u in links[v]:
        if u == p:
            children_dists.append(pd)
            continue
        children_dists.append(stones[u] + dists[u])

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, pd)
    if m == 0 and all(h >= d for d in children_dists):
        ans.append(h)

    for u in links[v]:
        if u == p:
            continue
        if len(links[u]) > 1:
            us = stones[u]
            second_dfs(u, v, sd - us - dists[u] + (all_stones - us), ans)


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
ans = []
second_dfs(0, -1, 0, ans)
if ans:
    print(min(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, pd):
    children_dists = []
    vs = stones[v]

    for u in links[v]:
        if u == p:
            children_dists.append(pd)
            continue
        children_dists.append(stones[u] + dists[u])

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, ps, pd)
    if m == 0 and all(h >= d for d in children_dists):
        print(h)
        exit()

    for u in links[v]:
        if u == p:
            continue
        if len(links[u]) > 1:
            second_dfs(u, v, sd - stones[u] - dists[u] + (all_stones - stones[u]))


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
second_dfs(0, -1, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, ps, pd):
    if len(links[v]) == 1:
        return

    children_dists = []
    vs = stones[v]
    vd = dists[v]

    for u in links[v]:
        if u == p:
            if p != -1:
                pdf = all_stones - vs - vd + (all_stones - vs)
                children_dists.append(pdf)
            continue
        children_dists.append(dists[u] + stones[u])
        second_dfs(u, v, vs, vd)

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, ps, pd)
    if m == 0 and all(h >= d for d in children_dists):
        print(h)
        exit()


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, ps, pd):
    if len(links[v]) == 1:
        return

    children_dists = []
    vs = stones[v]
    vd = dists[v]

    for u in links[v]:
        if u == p:
            if p != -1:
                pdf = pd - vs - vd + (all_stones - vs)
                children_dists.append(pdf)
            continue
        children_dists.append(dists[u] + stones[u])
        second_dfs(u, v, vs, vd)

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, ps, pd)
    if m == 0 and all(h >= d for d in children_dists):
        print(h)
        exit()


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
d = dict()
ans = 10**9
if s.count("1") == 1:
  print(0)
  exit()
for i in range(n):
  d[i] = []
for _ in range(n-1):
  a,b = map(int, input().split())
  d[a-1].append(b-1)
  d[b-1].append(a-1) 
for root in range(n):
  if len(d[root]) == 1:
    continue
  ll = [10**4]*n
  ll[root] = 0
  curl = []
  for x in d[root]:
    ll[x] = 1
    q = [x]
    seen = set([root])
    xs = 0
    while q:
      cur = q.pop()
      if s[cur] == "1":
        xs += ll[cur]
      seen.add(cur)
      for i in set(d[cur])-seen:
        ll[i] = ll[cur] + 1
        q.append(i)
    curl.append(xs)
  if sum(curl)%2:
    continue
  t = sum(curl)//2
  if all([j<=t for j in curl]):
    if ans > t:
      ans = t
if ans > 10**8:
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, ps, pd):
    if len(links[v]) == 1:
        return

    children_dists = []
    vs = stones[v]
    vd = dists[v]

    for u in links[v]:
        if u == p:
            if p != -1:
                pdf = pd - vs - vd + (ps - vs)
                children_dists.append(pdf)
            continue
        children_dists.append(dists[u] + stones[u])
        second_dfs(u, v, vs, vd)

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists, ps, pd)
    if m == 0 and all(h >= d for d in children_dists):
        print(h)
        exit()


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones == 1:
    print(0)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

ps = 0
v_to = [[] for i in range(N)]

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

def dfs(id, fr, di):
    global ps
    if S[id] == '1':
        ps += di
    for t in v_to[id]:
        if t != fr:
            dfs(t, id, di + 1)

cnt = 0
for i in range(N):
    if S[i] == '1':
        cnt += 1
        dfs(i, i, 0)

if cnt == 1:
    print(0)
else:
    if ps % (4 * cnt - 4) != 0:
        print(-1)
    else:
        print(ps // (4 * cnt - 4))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)


def first_dfs(v, p, stones, dists):
    stone = s[v]
    dist = 0
    for u in links[v]:
        if u == p:
            continue
        us, ud = first_dfs(u, v, stones, dists)
        stone += us
        dist += ud + us
    stones[v] = stone
    dists[v] = dist
    return stone, dist


def second_dfs(v, p, ps, pd):
    children_dists = []
    vs = stones[v]
    vd = dists[v]

    for u in links[v]:
        if u == p:
            if p != -1:
                ps -= vs
                pdf = pd - vs - vd + (ps - vs)
                children_dists.append(pdf)
            continue
        children_dists.append(dists[u] + stones[u])
        second_dfs(u, v, vs, vd)

    sd = sum(children_dists)
    h, m = divmod(sd, 2)
    # print(v, p, sd, h, m, children_dists)
    if m == 0 and all(h >= d for d in children_dists):
        print(h)
        exit()


n = int(input())
s = list(map(int, input()))
all_stones = sum(s)
if all_stones < 2:
    print(-1)
    exit()
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)
# print(links)
stones = [0] * n
dists = [0] * n
first_dfs(0, -1, stones, dists)
# print(stones)
# print(dists)
second_dfs(0, -1, 0, 0)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

ps = 0
v_to = [[] for i in range(N)]

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

def dfs(id, fr, di):
    global ps
    if S[id] == '1':
        ps += di
    for t in v_to[id]:
        if t != fr:
            dfs(t, id, di + 1)

cnt = 0
for i in range(N):
    if S[i] == '1':
        cnt += 1
        dfs(i, i, 0)

print(ps)
if ps % (2 * cnt) != 0:
    print(-1)
else:
    print(ps // (2 * cnt))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
d = dict()
ans = 10**9
if s.count("1") == 1:
  print(0)
  exit()
for i in range(n):
  d[i] = []
for _ in range(n-1):
  a,b = map(int, input().split())
  d[a-1].append(b-1)
  d[b-1].append(a-1) 
for root in range(n):
  if len(d[root]) == 1:
    continue
  ll = [10**4]*n
  ll[root] = 0
  curl = []
  for x in d[root]:
    ll[x] = 1
    q = [x]
    seen = set([root])
    xs = int(s[x])
    while q:
      cur = q.pop()
      if s[cur] == "1":
        xs += ll[cur]
      seen.add(cur)
      for i in set(d[cur])-seen:
        ll[i] = ll[cur] + 1
        q.append(i)
    curl.append(xs)
  if sum(curl)%2:
    continue
  t = sum(curl)//2
  if all([j<=t for j in curl]):
    if ans > t:
      ans = t
if ans > 10**8:
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq

N = int(input())
S = np.fromiter(map(int, input()), np.int)
E = [[] for i in range(N)]

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


min_score = -1

for v in range(N):
	visited = np.zeros(N, np.bool)
	visited[v] = True
	scores = []
	for u in E[v]:
		stack = [(u, v, 1)]
		score = 0
		while stack:
			cur, prev, depth = stack.pop()
			if S[cur]:
				score += depth
			for nxt in E[cur]:
				if prev == nxt:
					continue
				stack.append((nxt, cur, depth+1))
		scores.append(score)
	sum_score = sum(scores)
	if sum_score % 2 == 0 and all(s <= sum_score - s for s in scores):
		if -1 == min_score:
			min_score = sum_score // 2
		else:
			min_score = min(min_score, sum_score // 2)

print(min_score)

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:
    ANS=LENGTH//(2*(OLLEN-1))
    for j in range(1,N+1):
        LL=0
        for ol in OL:
            LL+=DIS[j][ol]

        if LL==ANS*2:
            print(ANS)
            sys.exit()
else:
    print(-1)