# [ARC083C] Bichrome Tree

## 题目描述

[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.