Problem:
 Score : 700 points    Problem Statement 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.      Constraints  1 \leq N \leq 1  000  1 \leq P_i \leq i - 1  0 \leq X_i \leq 5  000         Inputs Input is given from Standard Input in the following format:  N  P_2  P_3  ...  P_N  X_1  X_2  ...  X_N       Outputs If it is possible to allocate colors and weights to the vertices so that the condition is satisfied, print POSSIBLE ; otherwise, print IMPOSSIBLE .        Sample Input 1 3
1 1
4 3 2      Sample Output 1 POSSIBLE  For example, the following allocation satisfies the condition:   Set the color of Vertex 1 to white and its weight to 2 .  Set the color of Vertex 2 to black and its weight to 3 .  Set the color of Vertex 3 to white and its weight to 2 .   There are also other possible allocations.       Sample Input 2 3
1 2
1 2 3      Sample Output 2 IMPOSSIBLE  If the same color is allocated to Vertex 2 and Vertex 3 , Vertex 2 cannot be allocated a non-negative weight.  If different colors are allocated to Vertex 2 and 3 , no matter which color is allocated to Vertex 1 , it cannot be allocated a non-negative weight.  Thus, there exists no allocation of colors and weights that satisfies the condition.       Sample Input 3 8
1 1 1 3 4 5 5
4 1 6 2 2 1 3 3      Sample Output 3 POSSIBLE       Sample Input 4 1

0      Sample Output 4 POSSIBLE

Solution (Python):


import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
P = [p-1 for p in LIST()]
X = LIST()

nodes = [[] for i in range(N)]
for i, p in enumerate(P):
    nodes[p].append(i+1)


W = [None] * N
def calc(u):
    
    if not nodes[u]:
        return (X[u], 0)

    A = []
    total = 0
    for v in nodes[u]:
        A.append(W[v])
        total += W[v][0] + W[v][1]
    
    
    n = len(A)
    dp = [set() for i in range(n+1)]
    dp[0].add(0)
    for i in range(n):
        a, b = A[i]
        for s in dp[i]:
            dp[i+1].add(s+a)
            dp[i+1].add(s+b)
    B = sorted(dp[n])
    idx = bisect_right(B, X[u]) - 1
    
    if idx == -1:
        print('IMPOSSIBLE')
        exit()
    a, b = X[u], total - B[idx]
    return (a, b)

def rec(u, prev):
    for v in nodes[u]:
        rec(v, u)
    W[u] = calc(u)
rec(0, -1)
print('POSSIBLE')

Solution (Python):
def main():
    n=int(input())
    p=list(map(int,input().split()))
    x=list(map(int,input().split()))
    
    child=[[] for _ in [0]*n]
    for i,j in enumerate(p):
        child[j-1].append(i+1)
    
    other=[0]*n
    
    for i in range(n-1,-1,-1):
        if child[i]==[]:
            continue
        dp=[-1]*(x[i]+1)
        dp[0]=0
        xx=x[i]
        for j in child[i]:
            dp2=[-1]*(xx+1)
            m=x[j]
            o=other[j]
            for k,l in enumerate(dp):
                if l==-1:
                    continue
                if k+m<=xx:
                    if dp2[k+m]!=-1:
                        dp2[k+m]=min(dp2[k+m],l+o)
                    else:
                        dp2[k+m]=l+o
                if k+o<=xx:
                    if dp2[k+o]!=-1:
                        dp2[k+o]=min(dp2[k+o],l+m)
                    else:
                        dp2[k+o]=l+m
            dp=dp2
        k=[j for j in dp if j!=-1]
        if k!=[]:
            other[i]=min(k)
        else:
            print("IMPOSSIBLE")
            break
    else:
        print("POSSIBLE")

if __name__ == '__main__':
	main()

Solution (Python):

from collections import deque, defaultdict
import copy
import bisect

import math
import heapq

import sys
def input():
	return sys.stdin.readline().strip()

N = int(input())
P = list(map(int, input().split()))
X = list(map(int, input().split()))

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


for i in range(N - 1):
	tree[P[i] - 1].append(i + 1)

sum_list = [0]*N
que = deque([0])
que2 = deque([0])
while len(que) > 0:
	node = que.popleft()
	if len(tree[node]) > 0:
		for edge in tree[node]:
			que.append(edge)
			que2.append(edge)

for i in range(N - 1, -1, -1):
	node = que2[i]
	if len(tree[node]) > 0:
		for edge in tree[node]:
			sum_list[node] += sum_list[edge]
	sum_list[node] += X[node]

score = [[0,0] for i in range(N)]
for i in range(N - 1, -1, -1):
	node = que2[i]
	if len(tree[node]) == 0:
		score[node] = [X[node], 0]
	else:
		rest = X[node]
		dp = [[0 for i in range(len(tree[node]) + 1)] for j in range(rest + 1)]
		dp[0][0] = 1
		for x in range(rest + 1):
			for n in range(1, len(tree[node]) + 1):
				dp[x][n] = 0
				if x - score[tree[node][n-1]][0] >= 0:
					dp[x][n] = dp[x - score[tree[node][n-1]][0]][n - 1]
				if x - score[tree[node][n-1]][1] >= 0:
					dp[x][n] = dp[x][n] | dp[x - score[tree[node][n-1]][1]][n - 1]
		judge = 0
		
		for x in range(rest, -1, -1):
			
			if dp[x][len(tree[node])] == 1:
				judge = 1
				under_sum = 0
				for n in range(len(tree[node])):
					under_sum += sum(score[tree[node][n]])
				under_sum += rest - x
				under_sum -= X[node]
				score[node] = [X[node], under_sum]
				break
		if judge == 0:
			print("IMPOSSIBLE")
			exit()
print("POSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
import numpy as np
sys.setrecursionlimit(10**6)

N = int(input())
graph = [[] for _ in range(N+1)] 
for i,p in enumerate(input().split(),2):
    graph[int(p)].append(i)
X = [None] + [int(x) for x in input().split()]

def dfs(v):
    
    child = []
    for w in graph[v]:
        c = dfs(w)
        if c is None:
            return None
        child.append(c)
    S = sum(a+b for a,b in child)
    x = X[v]
    dp = np.zeros(x+1, dtype=np.bool) 
    dp[0] = 1
    for a,b in child:
        prev = dp
        dp = np.zeros_like(prev)
        if a <= x:
            dp[a:] = prev[:x+1-a]
        if b <= x:
            dp[b:] |= prev[:x+1-b]
    nz = np.nonzero(dp)[0]
    if len(nz) == 0:
        return None
    return x, S - nz[-1]

answer = 'POSSIBLE' if dfs(1) is not None else 'IMPOSSIBLE'
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
p = list(map(int, input().split()))
p = [-1] + [q-1 for q in p]
c = [[] for _ in range(n)]
for i in range(1, n):
	c[p[i]].append(i)
x = list(map(int, input().split()))

def dfs(cur):
	dp = [10**10 for _ in range(x[cur]+1)]
	dp[0] = 0
	for v in c[cur]:
		z, w = dfs(v)
		
		for i in range(x[cur], -1, -1):
			if dp[i] < 10**10:
				tmp = dp[i]
				dp[i] = 10**10
				if i+z <= x[cur]:
					dp[i+z] = min(dp[i+z], tmp+w)
				if i+w <= x[cur]:
					dp[i+w] = min(dp[i+w], tmp+z)
	
	if min(dp) == 10**10:
		print("IMPOSSIBLE")
		sys.exit()
	return min(dp), x[cur]

dfs(0)
print("POSSIBLE")

Solution (Python):


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


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




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)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
N=int(input())
P=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
table=[[] for i in range(N)]
for i in range(N-1):
    table[P[i]-1].append(i+1)
dp=[0]*N 

def tree(pa):
    for i in table[pa]:
        tree(i)
    t=len(table[pa])
    if t==0:
        return
    T=set()
    s=0
    for i in range(t):
        x=table[pa][i]
        s+=X[x]+dp[x]
        if i==0:
            if X[x]<=X[pa]:
                T.add(X[x])
            if dp[x]<=X[pa]:
                T.add(dp[x])
            continue
        S=set()
        for k in T:
            if k+X[x]<=X[pa]:
                S.add(k+X[x])
            if k+dp[x]<=X[pa]:
                S.add(k+dp[x])
        T=S
    if len(T)==0:
        print('IMPOSSIBLE')
        sys.exit()
    dp[pa]=s-max(T)
    return

tree(0)    
print('POSSIBLE')

Solution (Python):
N=int(input())
P=[-1]+[int(i)-1 for i in input().split()]
X=[int(i) for i in input().split()]
Q=[[] for i in range(N)]
for i in range(1,N):
    Q[P[i]].append(i)
dp=[0 for i in range(N)]
INF=10**9+7
def solve(i):
    cur=[INF for j in range(X[i]+1)]
    cur[0]=0
    for j in Q[i]:
        solve(j)
        prv=[k for k in cur]
        cur=[INF for k in range(X[i]+1)]
        for acc in range(len(prv)):
            if prv[acc]<INF:
                if acc+X[j]<=X[i]:
                    cur[acc+X[j]]=min(cur[acc+X[j]],prv[acc]+dp[j])
                if acc+dp[j]<=X[i]:
                    cur[acc+dp[j]]=min(cur[acc+dp[j]],prv[acc]+X[j])
    dp[i]=min(cur)
solve(0)
if dp[0]<INF:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


def main():
    N = int(input())
    P = list(map(int, input().split()))
    P = [0] + P
    X = list(map(int, input().split()))

    Y = [0] * N
    children = [None] * N

    for i in range(N - 1, 0, -1):
        parent = P[i] - 1
        if children[parent] is None:
            children[parent] = []
        children[parent].append(i)


    for i in range(N - 1, -1, -1):
        if not children[i] is None:
            dp = []
            j_max = len(children[i])
            for j in range(j_max + 1):
                dp.append([0] * 5050)
            dp[0][0] = 1
            x_sum, y_sum = 0, 0
            for j in range(j_max):
                c = children[i][j]
                xc, yc = X[c], Y[c]
                x_sum += xc
                y_sum += yc
                for k in range(X[i] + 1):
                    if xc <= k and dp[j][k - xc] == 1:
                        dp[j + 1][k] = 1
                    if yc <= k and dp[j][k - yc] == 1:
                        dp[j + 1][k] = 1
            f = False
            for k in range(X[i], -1, -1):
                if dp[j_max][k] == 1:
                    Y[i] = x_sum + y_sum - k
                    f = True
                    break
            if not f:
                print('IMPOSSIBLE')
                return

    print('POSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):


import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    sset = set([tmp_sum])
    for child in childs:
        rest = child[0] - child[1]
        tmp_set = set(sset)
        for s in sset:
            if s + rest <= x:
                tmp_set.add(s+rest)
        sset = tmp_set

    return (tuple(sorted([x, total-max(sset)], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

if n == 1:
    print("POSSIBLE")
    exit()

for i in range(n):
    index = n-1-i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index]-1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index]-1].append(index)

print("POSSIBLE")

Solution (Python):
N=int(input())
G=[[] for i in range(N)]
for i,a in enumerate(input().split()):
  G[int(a)-1].append(i+1)

X=[int(i) for i in input().split()]
def dfs(x):
  s=len(G[x])
  if s==0:
    return (0,X[x])
  dp=[[False]*(X[x]+1) for i in range(s+1)]
  dp[0][0]=True
  S=0
  for i in range(s):
    p,q=dfs(G[x][i])
    S+=p+q
    for j in range(X[x]+1):
      if dp[i][j]:
        if j+p<=X[x]:
          dp[i+1][j+p]=True
        if j+q<=X[x]:
          dp[i+1][j+q]=True
  a=-1
  for j in range(X[x]+1)[::-1]:
    if dp[s][j]:
      a=j
      break
  if a<0:
    print("IMPOSSIBLE")
    exit()
  return (X[x],S-a)
dfs(0)
print("POSSIBLE")

Solution (Python):
n = int(input())
p = list(map(int,input().split()))
x = list(map(int,input().split()))
g = [[] for i in range(n)]
for i in range(n-1):
  g[p[i]-1].append(i+1)
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in g[x]:
    dfs(i,y+1)
dfs(0,0)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
INF = float("inf")
dp = [0]*n
for j,i in hukai:
  if len(g[i]) == 0:
    continue
  tmp = []
  MIN = 0
  MAX= 0
  for k in g[i]:
    tmp.append([dp[k],x[k]])
    MIN += min(dp[k],x[k])
    MAX += max(dp[k],x[k])
  d = {}
  d[MAX] = MIN
  for k in tmp:
    MIN = min(k)
    MAX = max(k)
    co = list(d.keys())
    co.sort(key = lambda x:-x)
    for l in co:
      d[l-MAX+MIN] = min(d.get(l-MAX+MIN, INF),d[l]-MIN+MAX)
  co = list(d.keys())
  co.sort()
  for l in co:
    if d[l] <= x[i]:
      dp[i] = l
      break
  else:
    print("IMPOSSIBLE")
    exit()
print("POSSIBLE")

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
Chi = defaultdict(lambda: [])
F = defaultdict(lambda: [])
N = int(input())
Par = [0] + [int(i)-1 for i in input().split()]
Dis = [-1]*N
X = inpl()
Col = [()]*N
for i in range(N):
    Chi[Par[i]].append(i)
Q = [0]
ctr = 0
while ctr < N:
    st = Q.pop()
    if not Chi[st]:
        continue
    for j in Chi[st]:
        Dis[j] = Dis[st] + 1
        ctr += 1
        Q.append(j)
Chi[0].remove(0)
mD = max(Dis)
for i in range(N):
    F[Dis[i]].append(i)
for d in range(mD, -1, -1):
    for i in F[d]:
        if not Chi[i]:
            Col[i] = (0,X[i])
            continue
        Su = 0
        H = defaultdict(lambda: 0)
        H[0] = 0
        for j in Chi[i]:
            a, b = Col[j]
            Su += a+b
            G = defaultdict(lambda: 0)
            for k in H.keys():
                if a + k <= X[i]:
                    G[a+k] = 1
                if b + k <= X[i]:
                    G[b+k] = 1
            H = G.copy()
            if not H:
                break
        else:
            Col[i] = (Su-max(H), X[i])
            continue
        break
    else:
        continue
    break
else:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Solution (Python):
N = int(input())
P = [0] + list(map(int, input().split()))
X = list(map(int, input().split()))

V = [[0, {0: True}, 0, 0] for i in range(N)]  
for i in range(1, N):
    V[P[i]-1][0] += 1

from collections import deque
Open = deque()
for i, v in enumerate(V):
    if v[0]==0:
        Open.append(i)

while len(Open)!=0:
    iv = Open.popleft()
    v = V[iv]
    if len(v[1]) == 0:
        print("IMPOSSIBLE")
        exit()
    v[3] = v[2] - max(v[1].keys())

    u = P[iv]-1
    if u==-1:
        print("POSSIBLE")
        
        exit()
    V[u][0] -= 1
    if V[u][0] == 0:
        Open.append(u)
    V[u][2] += X[iv] + v[3]
    newdic = {}
    for key, val in V[u][1].items():
        if key+X[iv] <= X[u]:
            newdic[key+X[iv]] = True
        if key+v[3] <= X[u]:
            newdic[key+v[3]] = True
    V[u][1] = newdic

raise ValueError

Solution (Python):
from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0

    A = []
    
    for c in C[i]:
        A.append(dfs(c))

    S = 0
    for a in A:
        S += sum(a)

    dp = [[False]*(X[i]+1) for j in range(len(A)+1)]
    dp[0][0] = True

    for j in range(len(A)):
        for k in range(X[i]+1):
            a, b = A[j]
            if a <= k and dp[j][k-a]:
                dp[j+1][k] = True
            elif b <= k and dp[j][k-b]:
                dp[j+1][k] = True
        if not any(dp[j+1]):
            print('IMPOSSIBLE')
            exit()

    b = 0
    for j in range(X[i], -1, -1):
        if dp[len(A)][j]:
            b = j
            break

    return X[i], S - b

dfs(1)
print('POSSIBLE')

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N=int(input())
P=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
table=[[] for i in range(N)]
for i in range(N-1):
    table[P[i]-1].append(i+1)
dp=[0]*N 

def tree(pa):
    for i in table[pa]:
        tree(i)
    t=len(table[pa])
    if t==0:
        return
    T=set()
    s=0
    for i in range(t):
        x=table[pa][i]
        s+=X[x]+dp[x]
        if i==0:
            if X[x]<=X[pa]:
                T.add(X[x])
            if dp[x]<=X[pa]:
                T.add(dp[x])
            continue
        S=set()
        for k in T:
            if k+X[x]<=X[pa]:
                S.add(k+X[x])
            if k+dp[x]<=X[pa]:
                S.add(k+dp[x])
        T=S
    if len(T)==0:
        print('IMPOSSIBLE')
        sys.exit()
    dp[pa]=s-max(T)
    return

tree(0)    
print('POSSIBLE')

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N=int(input())
P=[int(i) for i in input().split()]
X=[int(i) for i in input().split()]
table=[[] for i in range(N)]
for i in range(N-1):
    table[P[i]-1].append(i+1)
dp=[0]*N 

def tree(pa):
    for i in table[pa]:
        tree(i)
    t=len(table[pa])
    if t==0:
        return
    T=set()
    s=0
    for i in range(t):
        x=table[pa][i]
        s+=X[x]+dp[x]
        if i==0:
            if X[x]<=X[pa]:
                T.add(X[x])
            if dp[x]<=X[pa]:
                T.add(dp[x])
            continue
        S=set()
        for k in T:
            if k+X[x]<=X[pa]:
                S.add(k+X[x])
            if k+dp[x]<=X[pa]:
                S.add(k+dp[x])
        T=S
    if len(T)==0:
        print('IMPOSSIBLE')
        sys.exit()
    dp[pa]=s-max(T)
    return

tree(0)    
print('POSSIBLE')

Solution (Python):

from itertools import chain,product

N = int(input())

P = list(chain((0,), map(lambda x: int(x)-1,input().split())))
X = list(map(int,input().split()))

L = [list() for _ in range(N)]

debug = [None]*N

for i in reversed(range(N)):
  p = P[i]
  l = L[i]

  x = X[i]

  
  if len(l) < 10:
    m = -1
    for s in product(*l):
      n = sum(s)
      if n <= x:
        m = max(n,m)
    if m == -1:
      print('IMPOSSIBLE')
      exit()
    m = sum(chain.from_iterable(l)) - m
  else:
    offset = sum(min(t) for t in l)
    x -= offset
    if x < 0:
      print('IMPOSSIBLE')
      exit()
    dp = [False]*(x+1)
    dp[0] = True
    s = 0
    for a,b in l:
      d = abs(a-b)
      s += d
      for j in reversed(range(x-d+1)):
        dp[j+d] = dp[j+d] or dp[j]
    m = x
    while not dp[m]:
      m -= 1
    m = s-m
    m += offset
    x += offset

  debug[i] = (x,m)
  L[p].append((x,m))
  L[i] = None

print('POSSIBLE')

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    n = I()
    p = LI_()
    x = LI()
    e = collections.defaultdict(list)
    for i in range(n-1):
        e[p[i]].append(i+1)

    def f(i):
        if not e[i]:
            return [0,x[i]]
        a = 0
        xi = x[i]
        xi1 = xi + 1
        tx = [0] * xi1
        tx[0] = 1
        for c in e[i]:
            rc = f(c)
            if not rc:
                return
            a += sum(rc)
            tt = [0] * xi1
            for i in range(xi1):
                if tx[i] == 0:
                    continue
                for c in rc:
                    if i+c < xi1:
                        tt[i+c] = 1
            tx = tt
        for i in range(xi,-1,-1):
            if tx[i] == 1:
                return [xi, a-i]
        return

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

Solution (Python):

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


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




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)

Solution (Python):
n = int(input())
P = list(map(int, input().split()))
X = list(map(int, input().split()))

dp = [0]*n
child = [[] for i in range(n)]
for i in range(n-1):
    child[P[i]-1].append(i+1)

for i in range(n-1, -1, -1):
    if not child[i]:
        dp[i] = 0
    else:
        su = 0
        re = 0
        for c in child[i]:
            z = min(X[c], dp[c])
            su += z
        if su > X[i]:
            print("IMPOSSIBLE")
            exit(0)
        can = X[i] - su
        ss = set([0])
        for c in child[i]:
            z = min(X[c], dp[c])
            rest = max(X[c], dp[c]) - z
            re += rest
            pp = set(ss)
            for s in ss:
                if s + rest <= can:
                    pp.add(s + rest)
            ss = pp
        dp[i] = su + re - max(ss)
print("POSSIBLE")