分数: 700 点
问题陈述
你得到了一棵有根的树 N 顶点。 顶点已编号 1 to N,根为顶点 1。 每个顶点的父顶点 i 除了根是顶点 P_i。每个顶点,包括根,都有 没有孩子或恰好有两个孩子.
判断是否可以写入其中一个字符 X 和 Y 在给定树的每个顶点上满足以下条件。
条件: 对于树的每条边,考虑长度的字符串 2 通过按照从父级开始的顺序连接端点上写入的字符而获得 P_i 给孩子 i。其中 (N - 1) 这样得到的字符串,
- 正是 A 是
XX, - 正是 B 是
XY, - 正是 C 是
YX,和 - 没有
YY.
你有 T 测试用例解决。
约束
- T \geq 1
- N \geq 1
- 对于每个输入,总和 N 测试用例最多为 10^4.
- A \geq 0
- B \geq 0
- C \geq 0
- A + B + C = N - 1
- 1 \leq P_i < i \ \ (2 \leq i \leq N)
- 每个顶点 k \ (1 \leq k \leq N) 作为家长发生 P_i \ (2 \leq i \leq N) 总共零次或两次.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例 \mathrm{case}_i \ (1 \leq i \leq T) 的格式如下:
N A B C P_2 P_3 \cdots P_N
输出
打印 T 行。
的 i- 第行应包含 Yes 如果有办法写入满足条件的字符,并且 No 否则。
样本输入 1
3 7 2 2 2 1 1 2 2 3 3 7 0 2 4 1 1 2 2 3 3 7 2 0 4 1 1 2 2 4 4
示例输出 1
Yes Yes No
对于第一个测试用例,例如,如果您编写 XXYXYXX 在顶点上按此顺序 1 to 7,
- 从边缘 (1, 2),我们得到
XX, - 从边缘 (1, 3),我们得到
XY, - 从边缘 (2, 4),我们得到
XX, - 从边缘 (2, 5),我们得到
XY, - 从边缘 (3, 6),我们得到
YX,和 - 从边缘 (3, 7),我们得到
YX.
每个 XX, XY,和 YX 出现两次,因此满足条件。
对于第二种情况,满足条件的一种方法是编写 XYYXXXX.
对于第三种情况,没有办法满足条件。