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):

"""

https://atcoder.jp/contests/arc083/tasks/arc083_c

NもXも小さい→重みで場合分けできる？
白と黒は、片方が重み0でなくてはいけないという制約以外は独立
木dpを考える

dp[v][black][white] = vの子部分木の重みの和がそれぞれblとwhの時の割り当てが可能か
→bitsetとかも思いつくが、blかwhはX[i]になることを利用して計算量を削減する

重みは根のほうでいくらでも大きくできるが、小さくはできないことに注目

dp[v][color] = 頂点vをcolorにした場合の、colorでない頂点の合計の最小値
dp[v][black] を求めたい。黒にするためには、黒の合計がXi以下でなくてはならない
→それぞれの子から2通りの bl,whをもらう。うまく組み合わせて、blがXi以下を保ちつつ、whの最小値を出す

これは以下のようなdpで解ける
dpv[i][bl] = wh → i番目の子まで見て、blの合計がblの時のwhの最小値
O(子の数*Xi)で解けるので、全体ではO(N*max(X))ぐらいで解けるはず
→どうしてもblの合計がXi以下にならない場合、不可能

"""
import sys
from sys import stdin

def dfs(v,p):

    dpB = {}
    dpW = {}
    dpB[0] = 0
    dpW[0] = 0

    for nex in lis[v]:

        if nex != p:
            ndpB = {}
            ndpW = {}
        
            b1,w1,b2,w2 = dfs(nex,v)

            for b in dpB:
                if b+b1 > X[v]:
                    continue
                if b+b1 not in ndpB:
                    ndpB[b+b1] = float("inf")
                ndpB[b+b1] = min(ndpB[b+b1],dpB[b] + w1)
            for b in dpB:
                if b+b2 > X[v]:
                    continue
                if b+b2 not in ndpB:
                    ndpB[b+b2] = float("inf")
                ndpB[b+b2] = min(ndpB[b+b2],dpB[b] + w2)

            for w in dpW:
                if w+w1 > X[v]:
                    continue
                if w+w1 not in ndpW:
                    ndpW[w+w1] = float("inf")
                ndpW[w+w1] = min(ndpW[w+w1] , dpW[w] + b1)
            for w in dpW:
                if w+w2 > X[v]:
                    continue
                if w+w2 not in ndpW:
                    ndpW[w+w2] = float("inf")
                ndpW[w+w2] = min(ndpW[w+w2] , dpW[w] + b2)

            dpB = ndpB
            dpW = ndpW
    
    b1 = X[v]
    w1 = float("inf")
    for i in dpB:
        w1 = min(w1,dpB[i])
    w2 = X[v]
    b2 = float("inf")
    for i in dpW:
        b2 = min(b2,dpW[i])

    if w1 == float("inf") and b2 == float("inf"):
        print ("IMPOSSIBLE")
        sys.exit()

    print (dpB,dpW,file=sys.stderr)
    return b1,w1,b2,w2
                    

N = int(stdin.readline())

P = list(map(int,stdin.readline().split()))
X = list(map(int,stdin.readline().split()))

lis = [ [] for i in range(N) ]
for i in range(1,N):
    lis[i].append(P[i-1]-1)
    lis[P[i-1]-1].append(i)

print(dfs(0,0),file=sys.stderr)
print ("POSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(10**4)
N = int(input())
I = [[] for _ in range(N)]

i = 1
for a in list(map(int, input().split())):
  I[a-1].append(i)
  i += 1
X = list(map(int, input().split()))

def dfs(v,I,X):
  INF = 10**20
  DP = [INF for _ in range(X[v]+1)]
  DP[0] = 0
  for i in I[v]:
    x = X[i]
    y = dfs(i,I,X)
    if x < y:
      x,y = y,x  
    for a in range(X[v],-1,-1):
      if a-y >= 0:
        DP[a] = DP[a-y] + x
        if a-x >= 0:
          DP[a] = min(DP[a], DP[a-x] + y)
      else:
        DP[a] = INF
        
  ans = min(DP)
  
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()                        
    
  del DP, INF
  return ans

dfs(0,I,X)
print("POSSIBLE")

Solution (Python):
n = int(input())
p = [0,0] + list(map(int,input().split()))
x = [0] + list(map(int,input().split()))

child = [[] for _ in range(n+1)]
for i,pi in enumerate(p[2:],2):
    child[pi].append(i)

tp = []
stack = [1]
while(stack):
    i = stack.pop()
    tp.append(i)
    for ci in child[i]:
        stack.append(ci)

tp = tp[::-1]

cost = [[-1,-1] for _ in range(n+1)]
for i in tp:
    tot = 0
    mins = 0
    dif = []
    for ci in child[i]:
        a,b = cost[ci]
        if(a > b):
            a,b = b,a
        mins += a
        tot += a+b
        dif.append(b-a)

    if( mins > x[i]):
        print('IMPOSSIBLE')
        exit()

    dp = 1
    dp_max = (1<<(x[i] - mins+1)) - 1
    for di in dif:
        dp = (dp|(dp<<di))&dp_max

    max_dif = -1
    while(dp>0):
        dp//=2
        max_dif += 1

    a = x[i]
    b = tot - mins - max_dif
    cost[i] = [a,b]

print('POSSIBLE')

Solution (Python):
N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*(X[p]+1) for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, X[p]+1):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, X[p]+1):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')

Solution (Python):
N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*5001 for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1][:X[p]+1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
*p, = map(int, readline().split())
*x, = map(int, readline().split())

dp = [1]*n
z = [0]*n

for i in range(n-1,-1,-1):
    
    if dp[i]==0:
        
        
        
        print("IMPOSSIBLE")
        exit()

    y = dp[i].bit_length()-1
    

    if i == 0:
        
        
        print("POSSIBLE")
        exit()
    else:
        pi = p[i-1]-1
        v = dp[pi]
        dp[pi] = ((v<<x[i]) | (v<<(z[i]-y))) & ((1<<(x[pi]+1))-1)
        z[pi] += x[i]+z[i]-y

Solution (Python):
n = int(input())
parents = list(map(int, input().split()))
weights = list(map(int, input().split()))

children = [[] for _ in range(n)]
for i in range(n-1):
    children[parents[i]-1].append(i+1)


def dfs(cur):
    if children[cur] == []:
        return (weights[cur], 0)

    sum = 0
    dp = [[False] * (weights[cur] + 1) for _ in range(len(children[cur])+1)]
    dp[0][0] = True
    for i, child in enumerate(children[cur]):
        x, y = dfs(child)
        sum += x + y
        for j in range(weights[cur] + 1):
            if j + x <= weights[cur]:
                dp[i+1][j+x] += dp[i][j]
            if j + y <= weights[cur]:
                dp[i+1][j+y] += dp[i][j]

    tmp = -1
    for i in range(weights[cur]+1):
        if dp[-1][i]:
            tmp = i
    
    if tmp == -1:
        print('IMPOSSIBLE')
        exit()

    else:
        return (weights[cur], sum-tmp)

dfs(0)
print('POSSIBLE')

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:
        child_sum_min = 0
        child_sum_rest = 0
        change_candidate = set([0]) 
        for c in child[i]:
            z = min(X[c], dp[c])
            child_sum_min += z
        if child_sum_min > X[i]:
            print('IMPOSSIBLE')
            exit()
        change_space = X[i] - child_sum_min
        for c in child[i]:
            z = min(X[c], dp[c])
            rest = max(X[c], dp[c]) - z
            child_sum_rest += rest
            tmp = set(change_candidate)
            for num in change_candidate:
                if num + rest <= change_space:
                    tmp.add(num + rest)
            change_candidate = tmp
        dp[i] = child_sum_min + child_sum_rest - max(change_candidate)

print('POSSIBLE')

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    inf = 5000001
    
    N = int(f_i.readline())
    P = map(int, f_i.readline().split())
    X = tuple(map(int, f_i.readline().split()))
    
    
    C = [[] for i in range(N)]
    for c, p in enumerate(P, start=1):
        C[p-1].append(c) 
    
    Y = [inf] * N
    
    
    
    def dfs(v):
        for c in C[v]:
            dfs(c)
        
        X_v = X[v]
        dp1 = [0] * (X_v + 1)
        dp2 = [inf] * (X_v + 1)
        for c in C[v]:
            X_c = X[c]
            Y_c = Y[c]
            for i, b in zip(range(X_c, X_v + 1), dp1):
                if b != inf:
                    dp2[i] = b + Y_c
            for i, w, dp2_i in zip(range(Y_c, X_v + 1), dp1, dp2[Y_c:]):
                tmp = w + X_c
                if tmp < dp2_i:
                    dp2[i] = tmp
            
            dp1 = dp2
            dp2 = [inf] * (X_v + 1)
        
        Y_v = min(dp1)
        Y[v] = Y_v
        return Y_v
    
    ans = dfs(0)
    if ans == inf:
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
    
solve()

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

INF = 2**30
n = int(input())
P = tuple(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = tuple(map(int, input().split()))
D = [-1]*n
def dfs(v):
  if D[v] != -1:
    return D[v]
  l = len(T[v])
  x = X[v]
  dp = np.full(x+1, INF, dtype=np.int64)
  dp[0] = 0
  for i, nv in enumerate(T[v]):
    k = np.full(x+1, INF, dtype=np.int64)
    d = dfs(nv)
    if x+1 >= X[nv]:
      np.minimum(k[X[nv]:], dp[:x+1-X[nv]]+d, out=k[X[nv]:])
    if x+1 >= d:
      np.minimum(k[d:], dp[:x+1-d]+X[nv], out=k[d:])
    dp = k.copy()
  res = dp.min()
  D[v] = res
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
import sys

sys.setrecursionlimit(10**6)

N=int(input())
P=list(map(int,input().split()))
child=[[] for i in range(N)]
for i in range(N-1):
    child[P[i]-1].append(i+1)

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

dpb=[float("inf") for i in range(N)]
dpw=[float("inf") for i in range(N)]

def dfs(v):
    for nv in child[v]:
        dfs(nv)
    if child[v]:
        subdpb=[[float("inf") for i in range(0,X[v]+1)] for j in range(len(child[v]))]
        subdpw=[[float("inf") for i in range(0,X[v]+1)] for j in range(len(child[v]))]
        for i in range(X[v]+1):
            nv=child[v][0]
            if i>=X[nv]:
                subdpb[0][i]=min(subdpb[0][i],dpb[nv])
            if i>=dpw[nv]:
                subdpb[0][i]=min(subdpb[0][i],X[nv])
        for i in range(1,len(child[v])):
            nv=child[v][i]
            for j in range(X[nv],X[v]+1):
                subdpb[i][j]=min(subdpb[i][j],subdpb[i-1][j-X[nv]]+dpb[nv])
            if dpw[nv]!=float("inf"):
                for j in range(dpw[nv],X[v]+1):
                    subdpb[i][j]=min(subdpb[i][j],subdpb[i-1][j-dpw[nv]]+X[nv])

        for i in range(X[v]+1):
            nv=child[v][0]
            if i>=X[nv]:
                subdpw[0][i]=min(subdpw[0][i],dpw[nv])
            if i>=dpb[nv]:
                subdpw[0][i]=min(subdpw[0][i],X[nv])
        for i in range(1,len(child[v])):
            nv=child[v][i]
            for j in range(X[nv],X[v]+1):
                subdpw[i][j]=min(subdpw[i][j],subdpw[i-1][j-X[nv]]+dpw[nv])
            if dpb[nv]!=float("inf"):
                for j in range(dpb[nv],X[v]+1):
                    subdpw[i][j]=min(subdpw[i][j],subdpw[i-1][j-dpb[nv]]+X[nv])

        dpb[v]=subdpb[-1][X[v]]
        dpw[v]=subdpw[-1][X[v]]

    else:
        dpb[v]=0
        dpw[v]=0

dfs(0)

if min(dpb[0],dpw[0])==float("inf"):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

INF = 2**30
n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = tuple(map(int, input().split()))
D = [-1]*n
def dfs(v):
  if D[v] != -1:
    return D[v]
  l = len(T[v])
  x = X[v]
  dp = [INF]*(x+1)
  dp[0] = 0
  for nv in T[v]:
    k = [INF]*(x+1)
    d = dfs(nv)
    for j in range(x+1):
      if j >= X[nv]:
        k[j] = min(k[j], dp[j-X[nv]]+d)
      if j >= d:
        k[j] = min(k[j], dp[j-d]+X[nv])
    dp = tuple(k)
  res = min(dp)
  D[v] = res
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

INF = 2**30
n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = tuple(map(int, input().split()))
D = [-1]*n
def dfs(v):
  if D[v] != -1:
    return D[v]
  l = len(T[v])
  x = X[v]
  dp = [INF]*(x+1)
  dp[0] = 0
  for nv in T[v]:
    k = [INF]*(x+1)
    d = dfs(nv)
    for j in range(x+1):
      if j >= X[nv]:
        k[j] = min(k[j], dp[j-X[nv]]+d)
      if j >= d:
        k[j] = min(k[j], dp[j-d]+X[nv])
    dp = tuple(k)
  res = min(dp)
  D[v] = res
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

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

INF = 2**30
n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [-1]*n
def dfs(v):
  if D[v] != -1:
    return D[v]
  l = len(T[v])
  x = X[v]
  dp = np.full(x+1, INF, dtype=np.int64)
  dp[0] = 0
  for i, nv in enumerate(T[v]):
    k = np.full(x+1, INF, dtype=np.int64)
    if x+1 >= X[nv]:
      np.minimum(k[X[nv]:], dp[:x+1-X[nv]]+dfs(nv), out=k[X[nv]:])
    if x+1 >= dfs(nv):
      np.minimum(k[dfs(nv):], dp[:x+1-dfs(nv)]+X[nv], out=k[dfs(nv):])
    dp = k.copy()
  res = dp.min()
  D[v] = res
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

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

INF = 2**30
n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [[-1]*n for _ in range(2)]
def dfs(color, v):
  if D[color][v] != -1:
    return D[color][v]
  l = len(T[v])
  x = X[v]
  dp = np.full(x+1, INF, dtype=np.int64)
  dp[0] = 0
  for i, nv in enumerate(T[v]):
    k = np.full(x+1, INF, dtype=np.int64)
    if x+1 >= X[nv]:
      np.minimum(k[X[nv]:], dp[:x+1-X[nv]]+dfs(color, nv), out=k[X[nv]:])
    if x+1 >= dfs(color^1, nv):
      np.minimum(k[dfs(color^1, nv):], dp[:x+1-dfs(color^1, nv)]+X[nv], out=k[dfs(color^1, nv):])
    dp = k.copy()
  res = dp.min()
  D[color][v] = res
  return res
ans = dfs(0, 0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [[-1]*n for _ in range(2)]
def dfs(color, v):
  if D[color][v] != -1:
    return D[color][v]
  l = len(T[v])
  x = X[v]
  dp = [[float("inf")]*(x+1) for _ in range(l+1)]
  dp[0][0] = 0
  for i, nv in enumerate(T[v]):
    for j in range(x+1):
      if j >= X[nv]:
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-X[nv]]+dfs(color, nv))
      if j >= dfs(color^1, nv):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-dfs(color^1, nv)]+X[nv])
  res = min(dp[l])
  D[color][v] = res
  return res
ans = dfs(0, 0)
if ans == float("inf"):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
from collections import Counter
n = int(input())
p = [0,0]+list(map(int,input().split()))
xls = [0]+list(map(int,input().split()))
dp = [[] for i in range(n+1)]
stack = []
cp = Counter(p)
deg = [cp[i] for i in range(n+1)]
def dp_sol(ls,s):
  l = len(ls)
  mnsm = sum(list(zip(*ls))[0])
  totsm = sum([sum(i) for i in ls])
  if mnsm > s:
    return 10**18
  dp = [[0 for i in range(s+1)] for j in range(l+1)]
  dp[0][0] = 1
  for i in range(1,l+1):
    mn,mx = ls[i-1]
    for j in range(mn,s+1):
      dp[i][j] |= dp[i-1][j-mn]
    for j in range(mx,s+1):
      dp[i][j] |= dp[i-1][j-mx]
  for i in range(s,-1,-1):
    if dp[l][i]:
      return totsm-i
for i in range(1,n+1):
  if cp[i] == 0:
    stack.append(i)
while stack:
  x = stack.pop()
  a = 0
  px = p[x]
  if dp[x]:
    a = dp_sol(dp[x],xls[x])
    if a == 10**18:
      print("IMPOSSIBLE")
      exit()
  if a < xls[x]:
    dp[px].append((a,xls[x]))
  else:
    dp[px].append((xls[x],a))
  deg[px] -= 1
  if deg[px] == 0:
    stack.append(px)
print("POSSIBLE")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
P = [-1] + LI()
X = LI()
G = [[] for _ in range(n)]
for i in range(1, n):
    G[P[i] - 1] += [i]
    G[i] += [P[i] - 1]

def check(u):
    total = 0
    bit  = 1
    for v in G[u]:
        if v == P[u] - 1:
            continue
        if len(G[v]) == 1:
            total += X[v]
            bit |= bit << X[v]
        else:
            a, b = check(v)
            total += a + b
            bit =  bit << a | bit << b
    c = bin(bit)
    for j in range(X[u], -1, -1):
        if bit >> j & 1:
            total += X[u] - j
            return X[u], total - X[u]
    else:
        print('IMPOSSIBLE')
        exit()


if check(0):
    print('POSSIBLE')

Solution (Python):

import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))
    X = list(map(int, args[2].split()))
    T = [[] for _ in range(n)]
    for i, p in enumerate(P):
        T[p-1].append(i+1)

    seq = []
    stack = [0]
    while stack:
        i = stack.pop()
        seq.append(i)
        for c in T[i]:
            stack.append(c)

    ret = 'POSSIBLE'
    inf = 2**32-1
    Y = [0]*n
    for i in seq[::-1]:
        prev = np.full(X[i]+1, inf, np.int64)
        prev[0] = 0
        for c in T[i]:
            cur = np.full(X[i]+1, inf, np.int64)
            x, y = X[c], Y[c]
            cur = np.minimum(
                np.concatenate((cur[:x], y+prev[:-x if 0 < x else len(prev)])),
                np.concatenate((cur[:y], x+prev[:-y if 0 < y else len(prev)]))
            )
            prev = np.copy(cur)

        y = np.min(prev)
        if y < inf:
            Y[i] = y
        else:
            ret = 'IMPOSSIBLE'
            break

    return ret


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):

from collections import defaultdict, deque

import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    P = list(map(int, args[1].split()))
    X = list(map(int, args[2].split()))

    T = defaultdict(set)
    for i, p in enumerate(P):
        T[p-1].add(i+1)

    stack = []
    Q = deque()
    Q.append(0)
    while Q:
        i = Q.popleft()
        stack.append(i)
        for c in T[i]:
            Q.append(c)

    ret = 'POSSIBLE'
    inf = 2**32-1
    Y = [0]*n
    for i in stack[::-1]:
        prev = np.full(X[i]+1, inf, np.int64)
        prev[0] = 0
        x_acc, y_acc = 0, 0
        for c in T[i]:
            cur = np.full(X[i]+1, inf, np.int64)
            x, y = X[c], Y[c]
            x_acc += x
            y_acc += y
            cur[x:] = np.minimum(cur[x:], y+prev[:-x if 0 < x else len(prev)])
            cur[y:] = np.minimum(cur[y:], x+prev[:-y if 0 < y else len(prev)])
            prev = np.copy(cur)

        y = np.min(prev)
        if y < inf:
            Y[i] = y
        else:
            ret = 'IMPOSSIBLE'
            break

    return ret


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
import sys
input = sys.stdin.readline


N = int(input())
graph = [[] for _ in range(N)]
P = list(map(int, input().split()))
Xs = list(map(int, input().split()))

for i, p in enumerate(P):
    graph[p-1].append(i+1)

stack = [0]
Scores = [[0, 0] for _ in range(N)]
Ind = [0]*N
ok = True
while stack and ok:
    p = stack[-1]
    if Ind[p] == len(graph[p]):
        stack.pop()
        Max = Xs[p]
        dp = [False]*(Max+1)
        dp[0] = True
        S = 0
        for ch in graph[p]:
            a, b = Scores[ch]
            S += a+b
            for x in reversed(range(Max+1)):
                dp[x] = (x >= a and dp[x-a]) or (x >= b and dp[x-b])
        to_ret = -1
        for x in reversed(range(Max+1)):
            if dp[x]:
                to_ret = S - x
                break
        if to_ret == -1:
            ok = False
        else:
            Scores[p] = [Max, to_ret]
    else:
        stack.append(graph[p][Ind[p]])
        Ind[p] += 1

print("POSSIBLE" if ok else "IMPOSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline


N = int(input())
graph = [[] for _ in range(N)]
P = list(map(int, input().split()))
Xs = list(map(int, input().split()))

for i, p in enumerate(P):
    graph[p-1].append(i+1)

stack = [0]
Scores = [[0, 0] for _ in range(N)]
Ind = [0]*N
ok = True
while stack and ok:
    p = stack[-1]
    if Ind[p] == len(graph[p]):
        stack.pop()
        Max = Xs[p]
        dp = [False]*(Max+1)
        dp[0] = True
        S = 0
        for ch in graph[p]:
            a, b = Scores[ch]
            S += a+b
            for x in reversed(range(Max+1)):
                dp[x] = (x >= a and dp[x-a]) or (x >= b and dp[x-b])
        to_ret = -1
        for x in reversed(range(Max+1)):
            if dp[x]:
                to_ret = S - x
                break
        if to_ret == -1:
            ok = False
        else:
            Scores[p] = [Max, to_ret]
    else:
        stack.append(graph[p][Ind[p]])
        Ind[p] += 1

print("POSSIBLE" if ok else "IMPOSSIBLE")

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

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

    child = [[] for _ in range(N+1)]
    par = [-1] * (N+1)
    for i, p in enumerate(P):
        child[p].append(i+2)
        par[i+2] = p
    child_num = [len(child[i]) for i in range(N+1)]
    st = []
    for i in range(1, N+1):
        if child_num[i] == 0:
            st.append(i)
    dp = [None] * (N+1)
    ok = 1
    while st:
        v = st.pop()
        x = X[v-1]
        if v != 1:
            p = par[v]
            child_num[p] -= 1
            if child_num[p] == 0:
                st.append(p)
        if not child[v]:
            dp[v] = (x, 0)
            continue
        dp2 = [[False] * (x+1) for _ in range(len(child[v])+1)]
        dp2[0][0] = True
        S = 0
        for i, u in enumerate(child[v]):
            a, b = dp[u]
            S += a+b
            for j in range(x+1):
                if dp2[i][j]:
                    if j + a <= x:
                        dp2[i+1][j+a] = True
                    if j+b <= x:
                        dp2[i+1][j+b] = True
        finish = 1
        for j in range(x, -1, -1):
            if dp2[-1][j]:
                dp[v] = (x, S-j)
                finish = 0
                break
        if finish:
            ok = 0
            break

    if ok:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
pp = LI()
xx = LI()
to = defaultdict(list)
ww = [[-1, -1] for _ in range(n)]

def dfs(u=0):
    if not len(to[u]):
        ww[u] = [xx[u], 0]
        return True
    ret_ww = set([0])
    uw = xx[u]
    sum_ret_w = 0
    for cu in to[u]:
        if not dfs(cu): return False
        new_ret_ww = set()
        for cuw in ww[cu]:
            sum_ret_w += cuw
            for ret_w in ret_ww:
                new_ret_w = ret_w + cuw
                if new_ret_w <= uw: new_ret_ww.add(new_ret_w)
        ret_ww = new_ret_ww
    if not ret_ww: return False
    ww[u] = [uw, sum_ret_w - max(ret_ww)]
    return True

def main():
    for u, p in enumerate(pp, 1):
        to[p - 1].append(u)
    
    if dfs():
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    

main()

Solution (Python):
from bisect import bisect_right

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

C = [[] for _ in range(N+1)]
for i in range(N-1):
    C[P[i]].append(i+2)
W = [(-1, -1)] * (N+1)

def solve(v):
    if not C[v]:
        return (X[v], 0)
    A = []
    total = 0
    for u in C[v]:
        A.append(W[u])
        total += sum(W[u])
    n = len(A)
    dp = [set() for _ in range(N+1)]
    dp[0].add(0)
    for i in range(n):
        x, y = A[i]
        for z in dp[i]:
            dp[i+1].add(x + z)
            dp[i+1].add(y + z)
    B = sorted(dp[n])
    idx = bisect_right(B, X[v]) - 1
    if idx == -1:
        print("IMPOSSIBLE")
        exit()
    x, y = X[v], total - B[idx]
    return (x, y)

def rec(v, prex):
    for u in C[v]:
        rec(u, v)
    W[v] = solve(v)

rec(1, 0)
print("POSSIBLE")

Solution (Python):
n=int(input())
p,x=[list(map(int,input().split())) for _ in [0]*2]
g=[[] for _ in [0]*n]
[g[j-1].append(i+1) for i,j in enumerate(p)]
d=[0]*n
q=[0]
while q:
 r=q.pop()
 for i in g[r]:
  if i!=0:
   d[i]=d[p[i-1]-1]+1
   q.append(i)
d=sorted([[-j,i] for i,j in enumerate(d)])
m=[[i,0] for i in x]
a,b=10003,5001
for _,i in d:
 y=x[i]+1
 e=[a]*y
 e[0]=0
 for j in g[i]:
  f=[a]*y
  p,q=m[j]
  for k in range(y-p):
   if e[k]!=a:f[k+p]=min(f[k+p],e[k]+q,b)
  for k in range(y-q):
   if e[k]!=a:f[k+q]=min(f[k+q],e[k]+p,b)
  e=f
 m[i][1]=min(e)
 if min(e)==a:
  print("IMPOSSIBLE")
  break
else:print("POSSIBLE")

Solution (Python):
def main():
    n=int(input())
    p=list(map(int,input().split()))
    x=list(map(int,input().split()))
    g=[[] for _ in [0]*n]
    [g[j-1].append(i+1) for i,j in enumerate(p)]
    dist=[0]*n
    q=[0]
    while q:
        qq=q.pop()
        for i in g[qq]:
            if i!=0:
                dist[i]=dist[p[i-1]-1]+1
                q.append(i)
    dist=sorted([[-j,i] for i,j in enumerate(dist)])
    dist=[j for i,j in dist]
    memo=[[i,0] for i in x]
    for i in dist:
        if len(g[i])==0:
            continue
        dp=[10003]*(x[i]+1)
        dp[0]=0
        for j in g[i]:
            dp2=[10003]*(x[i]+1)
            for k in range(x[i]-memo[j][0],-1,-1):
                if dp[k]!=10003:
                    dp2[k+memo[j][0]]=min(dp2[k+memo[j][0]],dp[k]+memo[j][1],5001)
            for k in range(x[i]-memo[j][1],-1,-1):
                if dp[k]!=10003:
                    dp2[k+memo[j][1]]=min(dp2[k+memo[j][1]],dp[k]+memo[j][0],5001)
            dp=dp2
        memo[i][1]=min(dp)
        if memo[i][1]==10003:
            print("IMPOSSIBLE")
            break
        
    else:
        print("POSSIBLE")
    

if __name__ == '__main__':
    main()

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]:
            if s <= 5000:
                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')