← 返回题目列表

AtCoder · arc157_e

E. XXYX 二叉树

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

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

对于第三种情况,没有办法满足条件。