分数: 700 点
问题陈述
我们有一棵树 N 顶点。 1 是树的根,也是 Vertex 的父级 i (2 \leq i \leq N) 是顶点 P_i.
对于树中的每个顶点,Snuke 都会分配一种颜色(黑色或白色)和一个非负整数权重。
Snuke 有一个最喜欢的整数序列, X_1, X_2, ..., X_N,所以他想分配颜色和权重,以便所有的都满足以下条件 v.
- 与颜色相同的顶点的总权重 v 在其根为的子树中包含的顶点中 v是 X_v.
在这里, 根为的子树 v 是由 Vertex 组成的树 v 及其所有后代。
确定是否可以通过这种方式分配颜色和权重。
约束
- 1 \leq N \leq 1 000
- 1 \leq P_i \leq i - 1
- 0 \leq X_i \leq 5 000
输入
输入由标准输入按以下格式给出:
N P_2 P_3 ... P_N X_1 X_2 ... X_N
输出
如果可以为顶点分配颜色和权重以满足条件,则打印 POSSIBLE;否则,打印 IMPOSSIBLE.
示例输入 1
3 1 1 4 3 2
示例输出 1
POSSIBLE
例如,以下分配满足条件:
- 设置顶点颜色 1 为白色,其重量为 2.
- 设置顶点颜色 2 为黑色,其重量为 3.
- 设置顶点颜色 3 为白色,其重量为 2.
还有其他可能的分配。
示例输入 2
3 1 2 1 2 3
示例输出 2
IMPOSSIBLE
如果相同的颜色分配给顶点 2 和顶点 3,顶点 2 无法分配非负权重。
如果为顶点分配不同的颜色 2 和 3,无论哪种颜色分配给Vertex 1,不能为其分配非负权重。
因此,不存在满足条件的颜色和权重分配。
示例输入 3
8 1 1 1 3 4 5 5 4 1 6 2 2 1 3 3
示例输出 3
POSSIBLE
示例输入 4
1 0
示例输出 4
POSSIBLE