YY が存在しないことから，Y が書き込まれた頂点は木上の独立集合（どの \(2\) つも互いに隣接しない頂点の集合）をなす必要があります． また，全ての頂点が \(0\) 個か \(2\) 個の子を持つことから，\(C\) の値は偶数である必要があります．

\(N = 1\) の場合，\(A = B = C = 0\) であり，この場合は X, Y のどちらを書き込んでも条件を満たすため，答えは Yes です． 以下では，\(N \ge 3\) の場合に条件を満たす書き込み方を考えます．

まず，YX が \(C\) 個あるので，葉（子を持たない頂点）以外に書き込まれた Y の個数は \(\displaystyle\frac{C}{2}\) である必要があります． また，根に書き込む文字によって，以下のいずれかが必要条件となります．

• 根に X を書き込んだ場合，書き込まれた Y の総数は \(B\) であり，そのうち葉に書き込まれた個数は \(B - \displaystyle\frac{C}{2}\) です．
• 根に Y を書き込んだ場合，書き込まれた Y の総数は \(B + 1\) であり，そのうち葉に書き込まれた個数は \(B - \displaystyle\frac{C}{2} + 1\) です．

逆に，以上の必要条件を全て満たす書き込み方であれば，自動的に元の条件（ XX が \(A\) 個，XY が \(B\) 個，YX が \(C\) 個，YY が \(0\) 個）を満たすことが確認できます．

したがって，「葉に合計 \(y\) 個の Y を書き込み，Y が書き込まれた頂点が独立集合をなすように文字を書き込むとき，全体で最大何個の Y を書き込めるか」が分かれば十分です． これは，\(\mathrm{dp}(v, y, z) \ \ (1 \le v \le N,\ 0 \le y \le \ell_v,\ z \in \{0, 1\})\) を「頂点 \(v\) を根とする部分木に関して，根に X \((z = 0)\), Y \((z = 1)\) を書き込むという条件下での上記の問題の答え」として，葉から根に向かう動的計画法 (DP) で計算できます． ここで，\(\ell_v\) は頂点 \(v\) を根とする部分木における葉の総数を表します． 葉の数は最大で \(\ell_1 = \displaystyle\frac{N+1}{2} \le 5000\) であり，全体の計算量は

\[\sum_{v = 1}^N \left(\left\lceil\frac{\ell_v}{2}\right\rceil + 1\right)^2 = \mathrm{O}(N^2)\]

で抑えられます．（いわゆる二乗の木 DP です．参考: ABC287-F Components など．）

実装例