Since there is no YY, the vertices with Ys written on them must form an independent set (a set of vertices, no two of which are adjacent) in the tree. Additionally, since every vertex has zero or two children, \(C\) must be even.

When \(N = 1\), we have \(A = B = C = 0\), in which case writing either X or Y satisfies the condition, so the answer is Yes. Below, assume \(N \ge 3\).

First, since there are \(C\) YXs, so there must be exactly \(\displaystyle\frac{C}{2}\) Ys written on non-leaf vertices (a leaf is a vertex without children). Additionally, depending on the character written on the root, one of the following must hold.

• If X is written on the root, exactly \(B\) Ys should be written in total, and exactly \(B - \displaystyle\frac{C}{2}\) of them should be written on leaves.
• If Y is written on the root, exactly \(B + 1\) Ys should be written in total, and exactly \(B - \displaystyle\frac{C}{2} + 1\) of them should be written on leaves.

On the other hand, if all of the necessary conditions above are satisfied, it can be seen that the original condition (\(A\) XXs, \(B\) XYs, \(C\) YX, and zero YYs) is automatically satisfied.

Thus, it is enough to know the maximum total number of Ys that can be written when exactly \(y\) Ys should be written on the leaves and the vertices with Ys written on them should form an independent set. You can compute this by dynamic programming (DP) from the leaves to the root where \(\mathrm{dp}(v, y, z) \ \ (1 \le v \le N,\ 0 \le y \le \ell_v,\ z \in \{0, 1\})\) is the answer to the above question for the subtree rooted at vertex \(v\) when writing X on the root if \(z = 0\) and Y if \(z = 1\). Here, \(\ell_v\) denotes the total number of leaves in the subtree rooted at vertex \(v\). There are at most \(\ell_1 = \displaystyle\frac{N+1}{2} \le 5000\) leaves, so the total complexity is

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

(This is the so-called square tree DP. See ABC287-F Components for instance.)

Sample implementation