E - XXYX Binary Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

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 \geq 1
  • N \geq 1
  • 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 回現れる．

入力

入力は以下の形式で標準入力から与えられる．

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 を出力せよ．

入力例 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

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 番目のテストケースについては，どのように書き込んでも条件を満たしません．

Score : 700 points

Problem Statement

You are given a rooted tree with N vertices. The vertices are numbered 1 to N, and the root is vertex 1. The parent of each vertex i except the root is vertex P_i. Each vertex, including the root, has no child or exactly two children.

Determine whether it is possible to write one of the characters X and Y on each vertex of the given tree to satisfy the following condition.

Condition: For each edge of the tree, consider the string of length 2 obtained by concatenating the characters written on the endpoints in the order from the parent P_i to the child i. Among the (N - 1) strings obtained in this way,

  • exactly A are XX,
  • exactly B are XY,
  • exactly C are YX, and
  • none is YY.

You have T test cases to solve.

Constraints

  • T \geq 1
  • N \geq 1
  • For each input, the sum of N over the test cases is at most 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)
  • Each vertex k \ (1 \leq k \leq N) occurs as a parent P_i \ (2 \leq i \leq N) zero times or twice in total.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_i \ (1 \leq i \leq T) is in the following format:

N A B C
P_2 P_3 \cdots P_N

Output

Print T lines. The i-th line should contain Yes if there is a way to write characters to satisfy the condition, and No otherwise.

Sample Input 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

Sample Output 1

Yes
Yes
No

For the first test case, if you, for instance, write XXYXYXX in this order on vertices 1 to 7,

  • from the edge (1, 2), we obtain XX,
  • from the edge (1, 3), we obtain XY,
  • from the edge (2, 4), we obtain XX,
  • from the edge (2, 5), we obtain XY,
  • from the edge (3, 6), we obtain YX, and
  • from the edge (3, 7), we obtain YX.

Each of XX, XY, and YX occurs twice, so the condition is satisfied.

For the second case, one way to satisfy the condition is to write XYYXXXX.

For the third case, there is no way to satisfy the condition.