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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
    # print(to)
    if dfs():
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    # print(ww)

main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
        #print(dp)
    else:
        print("POSSIBLE")
    #print(memo)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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[(i, j)] := (自分を根とした木の自分側の色の重み, 反対側の色の重み)
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
    # 自分の予定量より大きい重みしかなければNG
    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)
# 最後まで行けばOK
print('POSSIBLE')

Submission status: Accepted

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

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[(i, j)] := (自分を根とした木の自分側の色の重み, 反対側の色の重み)
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
    # 自分の予定量より大きい重みしかなければNG
    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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from collections import deque, defaultdict
import copy
import bisect
#sys.setrecursionlimit(10 ** 9)
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
		#print(dp)
		for x in range(rest, -1, -1):
			#print(x, len(tree[node]))
			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")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
		#print(cur, z, w)
		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)
	#print(cur, dp)
	if min(dp) == 10**10:
		print("IMPOSSIBLE")
		sys.exit()
	return min(dp), x[cur]

dfs(0)
print("POSSIBLE")

Submission status: Accepted

Solution code:
#copy for experience
# 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:
#copy for experience
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:
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")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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