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



Sample input:
3
1 1
4 3 2


Sample output:
POSSIBLE

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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)
#print(Open)
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")
        #print(V)
        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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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 #shiro

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

Submission status: Accepted

Solution code:

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]

  # len(l) < 10のとき全探索、それ以上はDP
  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')

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
# 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)

# solve knapsack
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)

Submission status: Accepted

Solution code:
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")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
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  # x >= y
    for a in range(X[v],y-1,-1):
      DP[a] = DP[a-y] + x
      if a-x >= 0:
        DP[a] = min(DP[a], DP[a-x] + y)
    for a in range(y-1, -1, -1):
      DP[a] = INF
  ans = min(DP)
  #print(DP, v)
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()
  return ans

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

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
M = 5000
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  # x >= y
    for a in range(X[v],y-1,-1):
      DP[a] = DP[a-y] + x
      if a-x >= 0:
        DP[a] = min(DP[a], DP[a-x] + y)
    for a in range(y-1, -1, -1):
      DP[a] = INF
  ans = min(DP)
  #print(DP, v)
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()
  return ans

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

Submission status: Runtime Error

Solution code:
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, 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])
  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')

Submission status: Runtime Error

Solution code:
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][1],dpb[nv])
            if i>=dpw[nv]:
                subdpb[0][i]=min(subdpb[0][1],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])
            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][1],dpw[nv])
            if i>=dpb[nv]:
                subdpw[0][i]=min(subdpw[0][1],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])
            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")

Submission status: Runtime Error

Solution code:
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 = 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 = [INF]*(x+1)
  dp[0] = 0
  for nv in T[v]:
    k = [INF]*(x+1)
    for j in range(x+1):
      if j >= X[nv]:
        k[j] = min(k[j], dp[j-X[nv]]+dfs(nv))
      if j >= dfs(nv):
        k[j] = min(k[j], dp[j-dfs(nv)]+X[nv])
    dp = k.copy()
  res = min(dp)
  D[v] = res
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Runtime Error

Solution code:
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)
    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]))]
    if child[v]:
        for i in range(X[v]+1):
            nv=child[v][0]
            if i>=X[nv]:
                subdpb[0][i]=min(subdpb[0][1],dpb[nv])
            if i>=dpw[nv]:
                subdpb[0][i]=min(subdpb[0][1],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])
            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][1],dpw[nv])
            if i>=dpb[nv]:
                subdpw[0][i]=min(subdpw[0][1],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])
            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")

Submission status: Runtime Error

Solution code:
# coding: utf-8
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]:
        dp = np.full(X[i]+1, inf, np.int64)
        dp[0] = 0
        x_acc, y_acc = 0, 0
        for c in T[i]:
            x, y = X[c], Y[c]
            x_acc += x
            y_acc += y
            dp = np.minimum(
                np.concatenate((dp[:x], dp[:-x]+y)),
                np.concatenate((dp[:y], dp[:-y if 0 < y else len(dp)]+x))
            )

        A = np.sort(dp[1:])
        if len(T[i]) == 0:
            Y[i] = 0
        elif A[0] < inf:
            Y[i] = A[0]
        elif y_acc != 0:
            ret = 'IMPOSSIBLE'
            break
        else:
            Y[i] = x_acc

    return ret


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

Submission status: Runtime Error

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

N = int(input())
graph = [[] for _ in range(N+1)] # parent to child
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):
    # None または 白、黒の2つ組を返す
    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) # 2択の繰り返しで作れる和
    dp[0] = 1
    for a,b in child:
        prev = dp
        dp = np.zeros_like(prev)
        dp[a:] = prev[:x+1-a]
        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)

Submission status: Runtime Error

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

N = int(input())
graph = [[] for _ in range(N+1)] # parent to child
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):
    # None または 白、黒の2つ組を返す
    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) # 2択の繰り返しで作れる和
    dp[0] = 1
    for a,b in child:
        prev = dp
        dp = np.zeros_like(prev)
        dp[a:] = prev[:-a]
        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)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

N = int(input())
graph = [[] for _ in range(N+1)] # parent to child
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):
    # None または 白、黒の2つ組を返す
    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) # 2択の繰り返しで作れる和
    dp[0] = 1
    for a,b in child:
        prev = dp
        dp = np.zeros_like(prev)
        dp[a:] = prev[:-a]
        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)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define REP(i,n) for (int i = 0; i < n; ++i)
#define REPR(i,n) for (int i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORE(x,xs) for (auto& x : xs)
#define MP make_pair
#define POSSIBLE "POSSIBLE"
#define IMPOSSIBLE "IMPOSSIBLE"

const int MAX = 1010;
const int MAX_X = 5050;
int N;
vi child[MAX];
int X[MAX];
int temp[2];
string ans;
bool dp[MAX_X];

void dfs(int n) {
    if (child[n].size() == 0) {
        temp[0] = 0; temp[1] = X[n];
        return;
    }

    REP (i, MAX_X) dp[i] = false;
    dp[0] = true;
    int S = 0, minSum = 0;
    int value = -1;
    FORE (v, child[n]) {
        dfs(v);
        S += temp[0] + temp[1];
        minSum += (temp[0], temp[1]);
        REPR (i, X[n]+1) if (dp[i]) {
            REP (k, 2) if (i + temp[k] <= X[n]) {
                value = max(value, i+temp[k]);
                dp[i+temp[k]] = true;
            }
        }
    }
    
    if (value == -1) {
        ans = IMPOSSIBLE;
    }
    temp[0] = X[n]; temp[1] = S-value;
}

int main () {
    cin >> N;
    ans = POSSIBLE;
    FOR (i, 2, N+1) {
        int p;
        cin >> p;
        child[p].push_back(i);
    }
    FOR (i, 1, N+1) cin >> X[i];

    dfs(1);
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
# 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)

# solve knapsack
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)

Submission status: Runtime Error

Solution code:
mport 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 = []
        tx = x[i]
        for c in e[i]:
            rc = f(c)
            if not rc:
                return
            tx += sum(rc)
            a.append(rc)
        xi = x[i]
        txx = xi
        s = set([c for c in a[0] if c <= txx])
        for cl in a[1:]:
            t = set()
            for c in s:
                for d in cl:
                    if c+d > txx:
                        continue
                    t.add(c+d)
            s = t
        if s:
            return [tx-xi, xi]
        return

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

Submission status: Runtime Error

Solution code:
mport 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 = []
        tx = x[i]
        for c in e[i]:
            rc = f(c)
            if not rc:
                return
            tx += x[c]
            a.append(rc)
        xi = x[i]
        txx = xi
        s = set([c for c in a[0] if c <= txx])
        for cl in a[1:]:
            t = set()
            for c in s:
                for d in cl:
                    if c+d > txx:
                        continue
                    t.add(c+d)
            s = t
        if s:
            return [tx-xi, xi]
        return

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())