AT_arc157_e.[ARC157E] XXYX Binary Tree

给定一棵有 $N$ 个顶点的有根树。每个顶点编号为 $1$ 到 $N$ 的互不相同的整数，根为顶点 $1$。对于除根以外的每个顶点 $i$，其父节点为顶点 $P_i$。对于每个顶点（包括根），要么没有子节点，要么恰好有 $2$ 个子节点。

请判断是否可以在给定的树的每个顶点上写入字符 X 或 Y，使得满足以下条件：

条件： 对于树的每一条边，考虑将其两个端点上写入的字符，按照从父节点 $P_i$ 到子节点 $i$ 的顺序排列，得到一个长度为 $2$ 的字符串。这样的字符串总共有 $N-1$ 个，其中：

• 恰好有 $A$ 个为 XX，
• 恰好有 $B$ 个为 XY，
• 恰好有 $C$ 个为 YX，
• 不存在 YY。

给定 $T$ 组测试数据，请分别回答每组数据是否存在满足条件的字符分配方案。

输入按以下格式从标准输入给出。

$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$ 行输出第 $i$ 个测试用例的答案。如果存在满足条件的字符分配方案，输出 Yes，否则输出 No。

限制条件

• $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)$ 出现的次数要么为 $0$ 次，要么为 $2$ 次

样例解释 1

对于第 $1$ 个测试用例，例如按顶点 $1$ 到 $7$ 的顺序写入 XXYXYXX，则

• 边 $(1, 2)$ 得到的字符串为 XX，
• 边 $(1, 3)$ 得到的字符串为 XY，
• 边 $(2, 4)$ 得到的字符串为 XX，
• 边 $(2, 5)$ 得到的字符串为 XY，
• 边 $(3, 6)$ 得到的字符串为 YX，
• 边 $(3, 7)$ 得到的字符串为 YX，

因此 XX、XY、YX 各有 $2$ 个，满足条件。

对于第 $2$ 个测试用例，例如写入 XYYXXXX 也能满足条件。

对于第 $3$ 个测试用例，无论如何分配字符都无法满足条件。

由 ChatGPT 4.1 翻译