比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
蜀山鸭梨大 | WAWWWWWWWW | 0.000 s | 0.00 MiB | 10 |
“如果这是无法抗拒的命运,那我想为你而活下去。因为我知道,人生会因此而更加光辉。”-- $\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
对于 $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
数据很难造,不过保证不存在“不可以,总司令”的情况。