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 翻译