比赛场次 615
比赛名称 2024暑假C班集训5
比赛状态 已结束比赛成绩
开始时间 2024-07-05 08:00:00
结束时间 2024-07-05 12:00:00
开放分组 全部用户
注释介绍 由于 COGS 特性,题目顺序完全乱序,请自行决策开题顺序。
组题人主观难度顺序:T2 < T1 < T4 < T3。
题目名称 Spirits
输入输出 spirits.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar蜀山鸭梨大 WAWWWWWWWW 0.000 s 0.00 MiB 10

Spirits

★★★   输入文件:spirits.in   输出文件:spirits.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目背景】

“如果这是无法抗拒的命运,那我想为你而活下去。因为我知道,人生会因此而更加光辉。”-- $\rm{Spirits - KOKIA}$

【题目描述】

珂朵莉给了你一棵含 $n$ 个结点,以 $1$ 号节点为根的有根树。$i$ 号节点的父节点为 $p_i$。

给定 $n$ 个整数 $X_1,X_2,\dots,X_n$,现在要将树上的每个结点染成黑色或白色,并赋上点权,点权须为非负整数。

珂朵莉想知道,是否存在一种赋权和染色方案,使得点 $i$ 子树中和点 $i$ 颜色相同的点(包括 $i$ 自身)权值和恰好为 $X_i$。

因为珂朵莉忙着给 Ynoi 出毒瘤数据结构题,所以这道简单题就交给你啦。

【输入格式】

本题每个测试点含多组测试数据。

第一行一个整数 $T$,表示数据组数。

每组测试数据中,第一行一个整数 $n$,表示树的结点数。

下面一行 $n-1$ 个整数,第 $i$ 个数表示 $p_{i+1}$。

接下来一行 $n$ 个整数,第 $i$ 个数表示 $X_i$。

【输出格式】

$T$ 行,若存在一种方案输出 $\rm{POSSIBLE}$,反之输出 $\rm{IMPOSSIBLE}$。

【样例输入】

4
3
1 1
4 3 2
3
1 2
1 2 3
8
1 1 1 3 4 5 5
4 1 6 2 2 1 3 3
1

0

【样例输出】

POSSIBLE
IMPOSSIBLE
POSSIBLE
POSSIBLE

【大样例】

大样例QAQ

【数据规模与约定】

对于 $20\%$ 的数据,$1\le T\le 2,1\le n \le 5,1\le X_i\le 5$。

对于 $100\%$ 的数据,$1\le n,\sum n\le 10^3,0\le X_i\le 5\times 10^3,1\le p_i\le i-1$

【来源】

ARC083E

数据很难造,不过保证不存在“不可以,总司令”的情况。