AtCoder Regular Contest 083 - Bichrome Tree

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-----
3
1 1
4 3 2

-----Sample Output-----
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.

Difficulty: HARD

Starter code:

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

def __starting_point():
	main()
__starting_point()


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

def __starting_point():
	main()
__starting_point()


N = int(input())
P_list = list(map(int, input().split()))
X_list = list(map(int, input().split()))
child_list = [[] for _ in range(N + 1)]
for i in range(2, N + 1):
	child_list[P_list[i - 2]].append(i)
color1 = [0] + X_list
color2 = [0] * (N + 1)

def solve_knapsack(L, M):
	min_acc = sum([min(color1[j], color2[j]) for j in L])
	if min_acc > M:
		return -1
	else:
		add_can = M - min_acc
		add_set = set([0])
		for j in L:
			add_j = max(color1[j], color2[j]) - min(color1[j], color2[j])
			add_set_ = set(add_set)
			for s in add_set:
				if s + add_j <= add_can:
					add_set_.add(s + add_j)
			add_set = add_set_
		total = sum([color1[j] + color2[j] for j in L])
		return total - max(add_set) - min_acc
res = 'POSSIBLE'
for i in range(N, 0, -1):
	if len(child_list[i]) == 0:
		pass
	elif len(child_list[i]) == 1:
		j = child_list[i][0]
		if min(color1[j], color2[j]) > X_list[i - 1]:
			res = 'IMPOSSIBLE'
			break
		elif max(color1[j], color2[j]) > X_list[i - 1]:
			color2[i] = max(color1[j], color2[j])
		else:
			color2[i] = min(color1[j], color2[j])
	else:
		c2 = solve_knapsack(child_list[i], X_list[i - 1])
		if c2 < 0:
			res = 'IMPOSSIBLE'
			break
		else:
			color2[i] = c2
print(res)


from itertools import chain, product
N = int(input())
P = list(chain((0,), [int(x) - 1 for x in input().split()]))
X = list(map(int, input().split()))
L = [list() for _ in range(N)]
debug = [None] * N
for i in reversed(list(range(N))):
	p = P[i]
	l = L[i]
	x = X[i]
	if len(l) < 10:
		m = -1
		for s in product(*l):
			n = sum(s)
			if n <= x:
				m = max(n, m)
		if m == -1:
			print('IMPOSSIBLE')
			return
		m = sum(chain.from_iterable(l)) - m
	else:
		offset = sum((min(t) for t in l))
		x -= offset
		if x < 0:
			print('IMPOSSIBLE')
			return
		dp = [False] * (x + 1)
		dp[0] = True
		s = 0
		for (a, b) in l:
			d = abs(a - b)
			s += d
			for j in reversed(list(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')


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


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

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


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


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


from collections import deque, defaultdict
import copy
import bisect
import math
import heapq
import sys

def input():
	return sys.stdin.readline().strip()
N = int(input())
P = list(map(int, input().split()))
X = list(map(int, input().split()))
tree = [[] for i in range(N)]
for i in range(N - 1):
	tree[P[i] - 1].append(i + 1)
sum_list = [0] * N
que = deque([0])
que2 = deque([0])
while len(que) > 0:
	node = que.popleft()
	if len(tree[node]) > 0:
		for edge in tree[node]:
			que.append(edge)
			que2.append(edge)
for i in range(N - 1, -1, -1):
	node = que2[i]
	if len(tree[node]) > 0:
		for edge in tree[node]:
			sum_list[node] += sum_list[edge]
	sum_list[node] += X[node]
score = [[0, 0] for i in range(N)]
for i in range(N - 1, -1, -1):
	node = que2[i]
	if len(tree[node]) == 0:
		score[node] = [X[node], 0]
	else:
		rest = X[node]
		dp = [[0 for i in range(len(tree[node]) + 1)] for j in range(rest + 1)]
		dp[0][0] = 1
		for x in range(rest + 1):
			for n in range(1, len(tree[node]) + 1):
				dp[x][n] = 0
				if x - score[tree[node][n - 1]][0] >= 0:
					dp[x][n] = dp[x - score[tree[node][n - 1]][0]][n - 1]
				if x - score[tree[node][n - 1]][1] >= 0:
					dp[x][n] = dp[x][n] | dp[x - score[tree[node][n - 1]][1]][n - 1]
		judge = 0
		for x in range(rest, -1, -1):
			if dp[x][len(tree[node])] == 1:
				judge = 1
				under_sum = 0
				for n in range(len(tree[node])):
					under_sum += sum(score[tree[node][n]])
				under_sum += rest - x
				under_sum -= X[node]
				score[node] = [X[node], under_sum]
				break
		if judge == 0:
			print('IMPOSSIBLE')
			return
print('POSSIBLE')


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


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


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


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


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


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


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


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


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


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


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


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

def __starting_point():
	print(solve(*open(0).read().splitlines()))
__starting_point()


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

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


N = int(input())
P = [0] + list(map(int, input().split()))
X = list(map(int, input().split()))
V = [[0, {0: True}, 0, 0] for i in range(N)]
for i in range(1, N):
	V[P[i] - 1][0] += 1
from collections import deque
Open = deque()
for (i, v) in enumerate(V):
	if v[0] == 0:
		Open.append(i)
while len(Open) != 0:
	iv = Open.popleft()
	v = V[iv]
	if len(v[1]) == 0:
		print('IMPOSSIBLE')
		exit()
	v[3] = v[2] - max(v[1].keys())
	u = P[iv] - 1
	if u == -1:
		print('POSSIBLE')
		exit()
	V[u][0] -= 1
	if V[u][0] == 0:
		Open.append(u)
	V[u][2] += X[iv] + v[3]
	newdic = {}
	for (key, val) in V[u][1].items():
		if key + X[iv] <= X[u]:
			newdic[key + X[iv]] = True
		if key + v[3] <= X[u]:
			newdic[key + v[3]] = True
	V[u][1] = newdic
raise ValueError


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


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


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


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

def __starting_point():
	print(solve(*open(0).read().splitlines()))
__starting_point()


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


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


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


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


import sys
sys.setrecursionlimit(10 ** 7)

def main1(n, p, x):
	ki = [[] for _ in range(n)]
	for (i, v) in enumerate(p):
		v -= 1
		i += 1
		ki[i].append(v)
		ki[v].append(i)

	def dfs(p, v):
		ary = []
		bs = 1
		sa = 0
		mina = 0
		for nv in ki[v]:
			if nv != p:
				(a, b) = dfs(v, nv)
				if a == -1:
					return (-1, -1)
				ary.append([a, b])
				nbs = 0
				nbs |= bs << a
				nbs |= bs << b
				mina += min(a, b)
				sa += a + b
				bs = nbs
		if mina > x[v]:
			return (-1, -1)
		for j in range(x[v], mina - 1, -1):
			if bs >> j & 1:
				return (x[v], sa - j)
		return (-1, -1)
	(a, b) = dfs(-1, 0)
	if a != -1:
		return True
	else:
		return False

def __starting_point():
	n = int(input())
	p = list(map(int, input().split()))
	x = list(map(int, input().split()))
	ret1 = main1(n, p, x)
	print('POSSIBLE' if ret1 else 'IMPOSSIBLE')
__starting_point()


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


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


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


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


import sys
input = sys.stdin.readline
import numpy as np
sys.setrecursionlimit(10 ** 6)
N = int(input())
graph = [[] for _ in range(N + 1)]
for (i, p) in enumerate(input().split(), 2):
	graph[int(p)].append(i)
X = [None] + [int(x) for x in input().split()]

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


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


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


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


n = int(input())
p = list(map(int, input().split()))
x = list(map(int, input().split()))
y = [0] * n
c = [[] for _ in [0] * n]
for i in range(n - 1):
	c[p[i] - 1] += [i + 1]
I = float('inf')
for i in range(n - 1, -1, -1):
	a = x[i]
	d = [0] * -~a
	for j in c[i]:
		for k in range(a, -1, -1):
			b = x[j]
			e = y[j]
			f = I if k - b < 0 else d[k - b] + e
			g = I if k - e < 0 else d[k - e] + b
			d[k] = min(f, g, I)
	y[i] = d[a]
print('POSSIBLE' if I > y[0] else 'IMPOSSIBLE')