配点: $700$ 点

問題文

$N$ 頂点からなる木があります。頂点 $1$ は木の根であり、頂点 $i$ ($2 \leq i \leq N$) の親は頂点 $P_i$ です。

すぬけ君は、この木の各頂点に白または黒の色と非負整数の重みを割り当てることにしました。

すぬけ君にはお気に入りの数列 $X_1, X_2, ..., X_N$ があります。そこで、色および重みの割り当てが、すべての $v$ について以下の条件を満たすようにしたいと考えました。

• 頂点 $v$ を根とする部分木に含まれる頂点のうち、頂点 $v$ と同じ色であるものの重みの和は $X_v$ である。

ここで、頂点 $v$ を根とする部分木とは、頂点 $v$ およびそのすべての子孫からなる木を指すものとします。

このような色および重みの割り当てが可能かどうか判定してください。

制約

• $1 \leq N \leq 1,000$
• $1 \leq P_i \leq i - 1$
• $0 \leq X_i \leq 5,000$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$P_2$ $P_3$ $...$ $P_N$

$X_1$ $X_2$ $...$ $X_N$

出力

条件を満たす色および重みの割り当てが可能である場合 POSSIBLE と、不可能である場合 IMPOSSIBLE と出力せよ。

3
1 1
4 3 2

POSSIBLE

たとえば、以下のような色と重みの割り当ては条件を満たします。

• 頂点 $1$ の色を白、重みを $2$ とする。
• 頂点 $2$ の色を黒、重みを $3$ とする。
• 頂点 $3$ の色を白、重みを $2$ とする。

他にも条件を満たす割り当て方は存在します。

3
1 2
1 2 3

IMPOSSIBLE

頂点 $2$ と頂点 $3$ に同じ色を割り当てる場合、頂点 $2$ に非負の重みを割り当てることができません。

頂点 $2$ と頂点 $3$ に異なる色を割り当てる場合、頂点 $1$ にどちらの色を割り当てても、非負の重みを割り当てることができません。

よって、条件を満たす色および重みの割り当て方は存在しません。

8
1 1 1 3 4 5 5
4 1 6 2 2 1 3 3

POSSIBLE

1

0

POSSIBLE