#P13650. [ARC157E] XXYX Binary Tree

    ID: 12852 传统题 3000ms 1024MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-树上背包状态维度消除子树合并剪除无效容量

[ARC157E] XXYX Binary Tree

题目描述

给定一棵有 NN 个顶点的有根树。每个顶点编号为 11 到 NN 的互不相同的整数,根为顶点 11。对于除根以外的每个顶点 ii,其父节点为顶点 PiP_i。对于每个顶点(包括根),要么没有子节点,要么恰好有 22 个子节点。

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

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

  • 恰好有 AA 个为 XX,
  • 恰好有 BB 个为 XY,
  • 恰好有 CC 个为 YX,
  • 不存在 YY。

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

输入格式

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

TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T

每组测试数据 casei (1≤i≤T)\mathrm{case}_i\ (1 \leq i \leq T) 格式如下:

N A B C P2 P3 ⋯ PNN\ A\ B\ C\ P_2\ P_3\ \cdots\ P_N

输出格式

输出 TT 行。第 ii 行输出第 ii 个测试用例的答案。如果存在满足条件的字符分配方案,输出 Yes,否则输出 No。

输入输出样例 #1

输入 #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

说明/提示

限制条件

  • T≥1T \geq 1
  • N≥1N \geq 1
  • 所有测试用例中 NN 的总和不超过 10410^4
  • A≥0A \geq 0
  • B≥0B \geq 0
  • C≥0C \geq 0
  • A+B+C=N−1A + B + C = N - 1
  • 1≤Pi<i (2≤i≤N)1 \leq P_i < i\ (2 \leq i \leq N)
  • 每个顶点 k (1≤k≤N)k\ (1 \leq k \leq N) 作为父节点 Pi (2≤i≤N)P_i\ (2 \leq i \leq N) 出现的次数要么为 00 次,要么为 22 次

样例解释 1

对于第 11 个测试用例,例如按顶点 11 到 77 的顺序写入 XXYXYXX,则

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

因此 XX、XY、YX 各有 22 个,满足条件。

对于第 22 个测试用例,例如写入 XYYXXXX 也能满足条件。

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