AT_arc083_c [ARC083E] Bichrome Tree

题目描述

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

输入格式

第一行,一个整数 $N$。 第二行,$N-1$ 个整数,从 $P_2$ 到 $P_N$。 第三行,$N$ 个整数,从 $X_1$ 到 $X_N$。

输出格式

如果有可行方案,输出 `POSSIBLE`。 否则,输出 `IMPOSSIBLE`。

说明/提示

- $1 \le N \le 1,000$ - $1 \le P_i \le i − 1$ - $0 \le X_i \le 5,000$