[ARC083E] Bichrome Tree

题意翻译

有一颗$N$个节点的树,其中1号节点是整棵树的根节点,而对于第$i$个点$(2≤i≤N)$,其父节点为$P_i$ 对于这棵树上每一个节点,Snuke将会给其染上黑色或白色,并给它赋一个权值。 Snuke有一个他最喜欢的整数序列,$X_1,X_2,\ldots,X_N$,他希望能够使得:对于每一个点$i$,都满足$i$的整颗子数内所有和$i$颜色相同的点(包括$i$本身)的点权和恰好为$X_i$。 现在给定你这棵树的结构和Snuke最喜欢的整数序列,请你判断是否有一种可行方案。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc083/tasks/arc083_c $ N $ 頂点からなる木があります。頂点 $ 1 $ は木の根であり、頂点 $ i $ ($ 2\ ≦\ i\ ≦\ N $) の親は頂点 $ P_i $ です。 すぬけ君は、この木の各頂点に白または黒の色と非負整数の重みを割り当てることにしました。 すぬけ君にはお気に入りの数列 $ X_1,\ X_2,\ ...,\ X_N $ があります。そこで、色および重みの割り当てが、すべての $ v $ について以下の条件を満たすようにしたいと考えました。 - 頂点 $ v $ を根とする部分木に含まれる頂点のうち、頂点 $ v $ と同じ色であるものの重みの和は $ X_v $ である。 ここで、頂点 $ v $ を根とする部分木とは、頂点 $ v $ およびそのすべての子孫からなる木を指すものとします。 このような色および重みの割り当てが可能かどうか判定してください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_2 $ $ P_3 $ $ ... $ $ P_N $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $

输出格式


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

输入输出样例

输入样例 #1

3
1 1
4 3 2

输出样例 #1

POSSIBLE

输入样例 #2

3
1 2
1 2 3

输出样例 #2

IMPOSSIBLE

输入样例 #3

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

输出样例 #3

POSSIBLE

输入样例 #4

1

0

输出样例 #4

POSSIBLE

说明

### 制約 - $ 1\ ≦\ N\ ≦\ 1,000 $ - $ 1\ ≦\ P_i\ ≦\ i\ -\ 1 $ - $ 0\ ≦\ X_i\ ≦\ 5,000 $ ### Sample Explanation 1 たとえば、以下のような色と重みの割り当ては条件を満たします。 - 頂点 $ 1 $ の色を白、重みを $ 2 $ とする。 - 頂点 $ 2 $ の色を黒、重みを $ 3 $ とする。 - 頂点 $ 3 $ の色を白、重みを $ 2 $ とする。 他にも条件を満たす割り当て方は存在します。 ### Sample Explanation 2 頂点 $ 2 $ と頂点 $ 3 $ に同じ色を割り当てる場合、頂点 $ 2 $ に非負の重みを割り当てることができません。 頂点 $ 2 $ と頂点 $ 3 $ に異なる色を割り当てる場合、頂点 $ 1 $ にどちらの色を割り当てても、非負の重みを割り当てることができません。 よって、条件を満たす色および重みの割り当て方は存在しません。