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

输入输出格式

输入格式


Input is given from Standard Input in the following format: ``` $ N $ $ P_2 $ $ P_3 $ $ ... $ $ P_N $ $ X_1 $ $ X_2 $ $ ... $ $ X_N $ ```

输出格式


If it is possible to allocate colors and weights to the vertices so that the condition is satisfied, print `POSSIBLE`; otherwise, print `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

输入样例 #5

3
1 1
4 3 2

输出样例 #5

POSSIBLE

输入样例 #6

3
1 2
1 2 3

输出样例 #6

IMPOSSIBLE

输入样例 #7

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

输出样例 #7

POSSIBLE

输入样例 #8

1

0

输出样例 #8

POSSIBLE

说明

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