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$