← 返回题目列表

AtCoder · arc083_c

E. 双色树

中文机器翻译题面 查看原题

分数: 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