Problem: We have a tree with N vertices. Vertex 1 is the root of the tree, and the parent of Vertex i (2 \leq i \leq N) is Vertex P_i.  To each vertex in the tree, Snuke will allocate a color, either black or white, and a non-negative integer weight.  Snuke has a favorite integer sequence, X_1, X_2, ..., X_N, so he wants to allocate colors and weights so that the following condition is satisfied for all v.    * The total weight of the vertices with the same color as v among the vertices contained in the subtree whose root is v, is X_v.  Here, _the subtree whose root is_ v is the tree consisting of Vertex v and all of its descendants.  Determine whether it is possible to allocate colors and weights in this way.

Submission attempts (in order):
# E
N = int(input())
P_list = list(map(int, input().split()))
X_list = list(map(int, input().split()))

# graph
child_list = [[] for _ in range(N+1)]
for i in range(2, N+1):
    child_list[P_list[i-2]].append(i)

# from root
# minimize local total weight

color1 = [0]+X_list
color2 = [0]*(N+1)


def solve_knapsack(L, M):
    min_acc = sum([min(color1[j], color2[j]) for j in L])
    if min_acc > M:
        return -1
    else:
        add_can = M - min_acc
        add_set = set([0])
        for j in L:
            add_j = max(color1[j], color2[j]) - min(color1[j], color2[j])
            add_set_ = set(add_set)
            for s in add_set:
                if s + add_j <= add_can:
                    add_set_.add(s + add_j)
            add_set = add_set_
        
        total = sum([color1[j]+color2[j] for j in L])
        return total - max(add_set)

res = "POSSIBLE"

for i in range(N, 0, -1):
    if len(child_list[i]) == 0:
        pass
    elif len(child_list[i]) == 1:
        j = child_list[i][0]
        if min(color1[j], color2[j]) > X_list[i-1]:
            res = "IMPOSSIBLE"
            break
        elif max(color1[j], color2[j]) > X_list[i-1]:
            color2[i] = max(color1[j], color2[j])
        else:
            color2[i] = min(color1[j], color2[j])
    else:
        c2 = solve_knapsack(child_list[i], X_list[i-1])
        if c2 < 0:
            res = "IMPOSSIBLE"
            break
        else:
            color2[j] = c2
    
print(res)

# E
N = int(input())
P_list = list(map(int, input().split()))
X_list = list(map(int, input().split()))

# graph
child_list = [[] for _ in range(N+1)]
for i in range(2, N+1):
    child_list[P_list[i-2]].append(i)

# from root
# minimize local total weight

color1 = [0]+X_list
color2 = [0]*(N+1)


def solve_knapsack(L, M):
    min_acc = sum([min(color1[j], color2[j]) for j in L])
    if min_acc > M:
        return -1
    else:
        add_can = M - min_acc
        add_set = set([0])
        for j in L:
            add_j = max(color1[j], color2[j]) - min(color1[j], color2[j])
            add_set_ = set(add_set)
            for s in add_set:
                if s + add_j <= add_can:
                    add_set_.add(s + add_j)
            add_set = add_set_
        
        total = sum([color1[j]+color2[j] for j in L])
        return total - max(add_set) - min_acc

res = "POSSIBLE"

for i in range(N, 0, -1):
    if len(child_list[i]) == 0:
        pass
    elif len(child_list[i]) == 1:
        j = child_list[i][0]
        if min(color1[j], color2[j]) > X_list[i-1]:
            res = "IMPOSSIBLE"
            break
        elif max(color1[j], color2[j]) > X_list[i-1]:
            color2[i] = max(color1[j], color2[j])
        else:
            color2[i] = min(color1[j], color2[j])
    else:
        c2 = solve_knapsack(child_list[i], X_list[i-1])
        if c2 < 0:
            res = "IMPOSSIBLE"
            break
        else:
            color2[i] = c2
    
print(res)

Verdicts: Runtime Error

Accepted