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

Solution code:
from collections import deque

N = int(input())
P = [i-1 for i in list(map(int, input().split()))]
C = [[] for _ in range(N)]
for i, p in enumerate(P, 1):
    C[p].append(i)
P = [-1] + P
X = list(map(int, input().split()))

# 今の頂点，各色の重み
dp = [[0] * 2 for _ in range(N)]
que = deque(i for i in range(N) if not C[i])
while que:
    v = que.popleft()
    c = C[v]
    n = len(c)
    res = 10 ** 9
    if not n:
        res = 0
    for i in range(1 << n):
        tmp = [0, 0]
        for j in range(n):
            if (i >> j):
                tmp[0] += dp[c[j]][0]
                tmp[1] += dp[c[j]][1]
            else:
                tmp[0] += dp[c[j]][1]
                tmp[1] += dp[c[j]][0]
        if tmp[0] > X[v]:
            continue
        res = min(res, tmp[1])
    if res == 10 ** 9:
        break
    dp[v][0] = X[v]
    dp[v][1] = res
    if P[v] == -1:
        continue
    que.append(P[v])

print('POSSIBLE' if dp[0][0] == X[0] else 'IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
plist=list(map(int,input().split()))
xlist=[0]+list(map(int,input().split()))

def dfs(u):
  if not graph[u]:
    return (xlist[u],0)
  
  ret=[]
  for v in graph[u]:
    ret.append(dfs(v))
    
  left_sum=right_sum=0
  for r in ret:
    if left_sum+r[0]<=xlist[u] and right_sum+r[1]<=xlist[u]:
      left_sum+=r[0]
      right_sum+=r[1]
    elif left_sum+r[1]<=xlist[u] and right_sum+r[0]<=xlist[u]:
      left_sum+=r[1]
      right_sum+=r[0]
    else:
      print("IMPOSSIBLE")
      sys.exit(0)
    
  #print(u,left_sum,right_sum)
  if left_sum<right_sum:
    return (left_sum,xlist[u])
  else:
    return (xlist[u],right_sum)

graph=[[] for _ in range(N+1)]
for i in range(N-1):
  p=plist[i]
  graph[p].append(i+2)
#print(graph)
#print(xlist)

result=dfs(1)
#print(result)
if min(result)<=xlist[1]:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Submission status: Wrong Answer

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(n - 1):
    G[P[i]] += [i + 1]
    G[i + 1] += [P[i]]

memo = [0] * n

def check(u):
    total1 = 0
    total2 = 0
    for v in G[u]:
        if v == P[u] - 1:
            continue
        if len(G[v]) == 1:
            total2 += X[v]
        else:
            a, b = check(v)
            total1 += min(a, b)
            total2 += max(a, b)
    if total1 <= X[u]:
        return X[u], total2
    else:
        print('IMPOSSIBLE')
        exit()


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import defaultdict, deque

import numpy as np


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

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

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

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

        y = np.min(dp)
        if y < inf:
            Y[i] = y
        elif y_acc <= X[i]:
            Y[i] = x_acc
        else:
            ret = 'IMPOSSIBLE'
            break

    return ret


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import defaultdict, deque

import numpy as np


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

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

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

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

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

    return ret


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from collections import defaultdict, deque

import numpy as np


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

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

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

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

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

    return ret


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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

leaves = [v-1 for v in range(1, N+1) if v not in set(P)]
stack = deque()
dp = [(0, 0) for _ in range(N)]
for l in leaves:
    dp[l] = (X[l], X[l])
    stack.appendleft((P[l]-1, l))

ans = "IMPOSSIBLE"
while stack:
    v, c = stack.pop()
    f = True
    if v == -1:
        continue
    if dp[c][0] <= X[v]:
        dp[v] = (X[v], dp[v][1])
        f = False
    if dp[c][1] <= X[v]:
        dp[v] = (dp[v][0], X[v])
        f = False
    if f:
        break
    stack.appendleft((P[v]-1, v))

if dp[0][0] == X[0] or dp[0][1] == X[0]:
    ans = "POSSIBLE"

print(ans)

Submission status: Wrong Answer

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)
        #print(dp)
    if memo[0][1]==10003:
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
    #print(memo)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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=[5001]*(x[i]+1)
        dp[0]=0
        for j in g[i]:
            dp2=[5001]*(x[i]+1)
            for k in range(x[i]-memo[j][0],-1,-1):
                dp2[k+memo[j][0]]=min(dp2[k+memo[j][0]],dp[k]+memo[j][1])
            for k in range(x[i]-memo[j][1],-1,-1):
                dp2[k+memo[j][1]]=min(dp2[k+memo[j][1]],dp[k]+memo[j][0])
            dp=dp2
        memo[i][1]=min(dp)
    if memo[0][1]==5001:
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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()))
y = [0 for _ in range(n)]

def dfs(cur):
	s = 0
	for v in c[cur]:
		s += dfs(v)
	if s > x[cur]:
		print("IMPOSSIBLE")
		sys.exit()
	y[p[cur]] += x[cur]
	return y[cur]

dfs(0)
print("POSSIBLE")

Submission status: Wrong Answer

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**15
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]],dp[j])
                if acc+dp[j]<=X[i]:
                    cur[acc+dp[j]]=min(cur[acc+dp[j]],X[j])
    dp[i]=min(cur)
solve(0)
if dp[0]<INF:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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**11
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]],dp[j])
                if acc+dp[j]<=X[i]:
                    cur[acc+dp[j]]=min(cur[acc+dp[j]],X[j])
    dp[i]=min(cur)
solve(0)
if dp[0]<INF:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Submission status: Wrong Answer

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:
                continue
        if a >= max_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: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
x = list(map(int,input().split()))
g = [[] for i in range(n)]
for i in range(n-1):
  g[p[i]-1].append(i+1)
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in g[x]:
    dfs(i,y+1)
dfs(0,0)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
INF = float("inf")
dp = [[INF]*(max(x)+3) for i in range(n)]
for i in range(n):
  dp[i][0] = 0
for j,i in hukai:
  if len(g[i]) == 0:
    dp[i][0] = 1
    continue
  tmp = []
  for k in g[i]:
    for l in range(5001):
      if dp[k]:
        tmp.append([x[k],dp[k][l]])
        break
  for l in range(x[i]+1):
    for k in tmp:
      if dp[i][l] != INF:
        if l + k[1] <=x[i]:
          dp[i][l+k[1]] = dp[i][l]+k[0]
        if l + k[0] <=x[i]:
          dp[i][l+k[0]] = dp[i][l]+k[1]
  for k in range(x[i]+1):
    if dp[i][k] != INF:
      break
    else:
      dp[i][k] = 0
  else:
    print("IMPOSSIBLE")
    exit()
print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
x = list(map(int,input().split()))
g = [[] for i in range(n)]
for i in range(n-1):
  g[p[i]-1].append(i+1)
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in g[x]:
    dfs(i,y+1)
dfs(0,0)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
INF = float("inf")
dp = [[INF]*5010 for i in range(n)]
for i in range(n):
  dp[i][0] = 0
for j,i in hukai:
  if len(g[i]) == 0:
    dp[i][0] = 1
    continue
  tmp = []
  for k in g[i]:
    for l in range(5001):
      if dp[k]:
        tmp.append([x[k],l])
        break
    else:
      print()
      exit()
  for l in range(x[i]+1):
    for k in tmp:
      if dp[i][l] != INF:
        if l + k[0] <=x[i]:
          dp[i][l+k[0]] = min(dp[i][l+k[0]],dp[i][l]+k[0])
        if l + k[1] <=x[i]:
          dp[i][l+k[1]] = min(dp[i][l+k[1]],dp[i][l]+k[1])
  for k in range(x[i]+1):
    if dp[i][k] <= x[i]:
      break
    else:
      dp[i][k] = 0
  else:
    print("IMPOSSIBLE")
    exit()
print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
n = int(input())
p = list(map(int,input().split()))
x = list(map(int,input().split()))
g = [[] for i in range(n)]
for i in range(n-1):
  g[p[i]-1].append(i+1)
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in g[x]:
    dfs(i,y+1)
dfs(0,0)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
omomi = [[0,0] for i in range(n)]
for j,i in hukai:
  if len(g[i]) == 0:
    omomi[i] = [x[i],0]
    continue
  MIN = 0
  MAX = 0
  for k in g[i]:
    MIN += min(omomi[k])
    MAX += max(omomi[k])
  if MIN <= x[i] and x[i] < MAX:
    omomi[i] = [x[i],MAX]
  elif x[i] >= MAX:
    omomi[i] = [x[i],MIN]
  else:
    print("IMPOSSIBLE")
    exit()
print("POSSIBLE")

Submission status: Wrong Answer

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
import sys
Chi = defaultdict(lambda: [])
F = defaultdict(lambda: [])
N = int(input())
Par = [0] + [int(i)-1 for i in input().split()]
Dis = [-1]*N
X = inpl()
Col = [()]*N
for i in range(N):
    Chi[Par[i]].append(i)
Q = [0]
ctr = 0
while ctr < N:
    st = Q.pop()
    if not Chi[st]:
        continue
    for j in Chi[st]:
        Dis[j] = Dis[st] + 1
        ctr += 1
        Q.append(j)
Chi[0].remove(0)
mD = max(Dis)
for i in range(N):
    F[Dis[i]].append(i)
for d in range(mD, -1, -1):
    H = defaultdict(lambda: 0)
    for i in F[d]:
        if not Chi[i]:
            Col[i] = (0,X[i])
            continue
        Su = 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:
            mh = max(H)
            Col[i] = (Su-mh, X[i])
            continue
        break
    else:
        continue
    break
else:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Submission status: Wrong Answer

Solution code:

from itertools import chain,product

N = int(input())

P = list(chain((0,), map(lambda x: int(x)-1,input().split())))
X = list(map(int,input().split()))

L = [list() for _ in range(N)]


for i in reversed(range(N)):
  p = P[i]
  l = L[i]

  x = X[i]

  # len(l) < 10のとき全探索、それ以上はDP
  if len(l) < 10:
    m = -1
    for s in product(*l):
      n = sum(s)
      if n <= x:
        m = max(n,m)
    if m == -1:
      print('IMPOSSIBLE')
      exit()
    m = sum(chain.from_iterable(l)) - m
  else:
    offset = sum(min(t) for t in l)
    x -= offset
    if x < 0:
      print('IMPOSSIBLE')
      exit()
    dp = [False]*(x+1)
    dp[0] = True
    s = 0
    for a,b in l:
      d = abs(a-b)
      s += d
      for i in range(x-d+1):
        dp[i+d] = dp[i+d] or dp[i]
    m = x
    while not dp[m]:
      m -= 1
    m = s-m
    m += offset
    x += offset


  L[p].append((x,m))

print('POSSIBLE')

Submission status: Wrong Answer

Solution code:

from itertools import chain,product

N = int(input())

P = list(chain((0,), map(lambda x: int(x)-1,input().split())))
X = list(map(int,input().split()))

L = [list() for _ in range(N)]

# 葉ノード探索
D = [0]*N
for p in P:
  D[p] += 1
D[0] -= 1
stack = [i for i,t in enumerate(D) if t==0]


while stack:
  i = stack.pop()
  p = P[i]
  l = L[i]

  x = X[i]

  # len(l) < 10のとき全探索、それ以上はDP
  if len(l) < 10:
    m = -1
    for s in product(*l):
      n = sum(s)
      if n <= x:
        m = max(n,m)
    if m == -1:
      print('IMPOSSIBLE')
      exit()
    m = sum(chain.from_iterable(l)) - m
  else:
    offset = sum(min(t) for t in l)
    x -= offset
    if x < 0:
      print('IMPOSSIBLE')
      exit()
    dp = [False]*(x+1)
    dp[0] = True
    s = 0
    for a,b in l:
      d = abs(a-b)
      s += d
      for i in range(x-d+1):
        dp[i+d] = dp[i+d] or dp[i]

    m = x
    while not dp[m]:
      m -= 1
    m = s-m
    m += offset


  L[p].append((x,m))
  D[p] -= 1
  if D[p] == 0:
    stack.append(p)

print('POSSIBLE')

Submission status: Wrong Answer

Solution code:

from itertools import chain

N = int(input())

P = list(chain((0,), map(lambda x: int(x)-1,input().split())))
X = list(map(int,input().split()))

dp = [0]*N

# 葉ノード探索
D = [0]*N
for p in P:
  D[p] += 1
D[0] -= 1
stack = [i for i,t in enumerate(D) if t==0]


while stack:
  i = stack.pop()
  p = P[i]

  a,b = sorted((X[i],dp[i]))

  xp = X[p]

  if b <= xp:
    dp[p] += a
  elif a <= xp:
    dp[p] += b
  else:
    print('IMPOSSIBLE')
    exit()

  D[p] -= 1
  if D[p] == 0:
    stack.append(p)

print('POSSIBLE')

Submission status: Wrong Answer

Solution code:

from itertools import chain

N = int(input())

P = list(chain((0,), map(lambda x: int(x)-1,input().split())))
X = list(map(int,input().split()))

L = [list() for _ in range(N)]

# 葉ノード探索
D = [0]*N
for p in P:
  D[p] += 1
D[0] -= 1
stack = [i for i,t in enumerate(D) if t==0]


while stack:
  i = stack.pop()
  p = P[i]
  l = L[i]

  x = X[i]
  m = 0
  for a,b in l:
    if b <= x:
      m += a
    elif a <= x:
      m += b
    else:
      print('IMPOSSIBLE')
      exit()
  L[p].append(tuple(sorted((x,m))))
  D[p] -= 1
  if D[p] == 0:
    stack.append(p)

print('POSSIBLE')

Submission status: Wrong Answer

Solution code:
# E
N = int(input())
P_list = list(map(int, input().split()))
X_list = list(map(int, input().split()))

# graph
child_list = [[] for _ in range(N+1)]
for i in range(2, N+1):
    child_list[P_list[i-2]].append(i)

# from root
# minimize local total weight

color1 = [0]+X_list
color2 = [0]*(N+1)

# solve knapsack
def solve_knapsack(L, M):
    min_acc = sum([min(color1[j], color2[j]) for j in L])
    if min_acc > M:
        return -1
    else:
        add_can = M - min_acc
        add_set = set([0])
        for j in L:
            add_j = max(color1[j], color2[j]) - min(color1[j], color2[j])
            add_set_ = set(add_set)
            for s in add_set:
                if s + add_j <= add_can:
                    add_set_.add(s + add_j)
            add_set = add_set_
        
        total = sum([color1[j]+color2[j] for j in L])
        return total - max(add_set)

res = "POSSIBLE"

for i in range(N, 0, -1):
    if len(child_list[i]) == 0:
        pass
    elif len(child_list[i]) == 1:
        j = child_list[i][0]
        if min(color1[j], color2[j]) > X_list[i-1]:
            res = "IMPOSSIBLE"
            break
        elif max(color1[j], color2[j]) > X_list[i-1]:
            color2[i] = max(color1[j], color2[j])
        else:
            color2[i] = min(color1[j], color2[j])
    else:
        c2 = solve_knapsack(child_list[i], X_list[i-1])
        if c2 < 0:
            res = "IMPOSSIBLE"
            break
        else:
            color2[i] = c2
    
print(res)

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

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

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

    if f(0):
        return 'POSSIBLE'

    return 'IMPOSSIBLE'


print(main())

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:
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 tx < xi:
            return
        if a <= xi:
            return [min(tx-xi, xi), tx]
        return

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

    return 'IMPOSSIBLE'


print(main())