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: Wrong Answer

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)
        e[i+1].append(p[i])

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

    if f(0,-1):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

Submission status: Wrong Answer

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)
        e[i+1].append(p[i])

    def f(i,k):
        if len(e[i]) < 2 and i > 0:
            return [0,x[i]]
        a = []
        xi = x[i]
        tx = xi
        for c in e[i]:
            if c == k:
                continue
            rc = f(c,i)
            if not rc:
                return
            tx += rc[1]
            a.append(rc[0])
        s = sum(a)
        if s < xi:
            return [min(tx-xi, xi), tx]
        return

    if f(0,-1):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

Submission status: Wrong Answer

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
        print(ss, can)
        dp[i] = su + re - max(ss)
print("POSSIBLE")

Submission status: Wrong Answer

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 = []
        xi = x[i]
        tx = xi
        for c in e[i]:
            rc = f(c)
            if not rc:
                return
            tx += rc[1]
            a.append(rc[0])
        s = sum(a)
        if s <= xi:
            return [min(tx-xi, xi), tx]
        return

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 i, nv in enumerate(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: Time Limit Exceeded

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()))
def dfs(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()
  return res
ans = dfs(0)
if ans == INF:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
            if a > x:
                break
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], 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: Time Limit Exceeded

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

    max_a, min_b = 0, 0
    for code in itertools.product([False, True], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
            if a > x:
                break
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], 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: Time Limit Exceeded

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

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (tuple(sorted([x, min_b], 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: Time Limit Exceeded

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

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (max([x, min_b]), min([x, min_b]))


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: Time Limit Exceeded

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

import itertools

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

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a, b = 0, 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
                b += childs[j][0]
            else:
                a += childs[j][0]
                b += childs[j][1]
        if a >= max_a and x >= a:
            max_a, min_b = a, b
            if max_a == x:
                break

    return (max([x, min_b]), min([x, min_b]))


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: Time Limit Exceeded

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


def mostProperComb(childs, x):
    if sum([c[1] for c in childs]) > x:
        print("IMPOSSIBLE")
        exit()
    loop = 2**len(childs)
    max_a, min_b = 0, 0
    for i in range(loop):
        a, b = 0, 0
        code = bin(loop-i-1)[2:].zfill(len(childs))
        for j, color in enumerate(code):
            if color == '1':
                a += childs[j][1]
                b += childs[j][0]
            elif color == '0':
                a += childs[j][0]
                b += childs[j][1]
        if a >= max_a and x >= a:
            max_a, min_b = a, b
            if max_a == x:
                break

    return (max([x, min_b]), min([x, min_b]))


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: Time Limit Exceeded

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)

    B = []
    for bits in range(2**(len(A))):
        a = 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            if a > X[i]:
                break
        if a <= X[i]:
            B.append(a)
    if not B:
        print('IMPOSSIBLE')
        exit()

    return X[i], S - max(B)

dfs(1)
print('POSSIBLE')

Submission status: Time Limit Exceeded

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

    B = []
    for bits in range(2**(len(A)-1)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

Submission status: Time Limit Exceeded

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 = set()
    for c in C[i]:
        A.add(dfs(c))

    B = []
    for bits in range(2**(len(A)-1)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

Submission status: Time Limit Exceeded

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

    B = []
    for bits in range(2**len(A)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

Submission status: Accepted

Solution code:

"""

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

Submission status: Accepted

Solution code:
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  # x >= y
    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)
  #print(DP, v)
  if ans >= INF:
    print("IMPOSSIBLE")
    sys.exit()                        
    
  del DP, INF
  return ans

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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):
    #print(i,x[i],(z[i],(dp[i].bit_length()-1)),bin(dp[i])[2::][::-1])
    if dp[i]==0:
        #print(i)
        #print(dp)
        #print(z)
        print("IMPOSSIBLE")
        exit()

    y = dp[i].bit_length()-1
    # (z[i]-y,y) を (z[i]-y,x)にするのが最善

    if i == 0:
        #print(dp)
        #print(z)
        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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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()))
    
    # Create lists of children
    C = [[] for i in range(N)]
    for c, p in enumerate(P, start=1):
        C[p-1].append(c) # Set vertex numbers to 0-based
    
    Y = [inf] * N
    
    # Perform a depth-first search in postorder
    # Execute dp in each sub-tree
    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()

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