We arbitrarily choose a root and consider it as a rooted tree. Then, we can solve this problem in \(\mathrm{O}(N)\) time by determining the colors from the leaves to the root.

From now on, let \(T\) be the color sequence before the operation that we want to find as the answer. Also, let \(R[i]\) denote the \(i\)-th character of the string \(R\) (the character corresponding to the color of vertex \(i\) in the color sequence \(R\)).

Conditions for the color after the operation

We consider whether the condition for vertex \(i\) (the color of vertex \(i\) after the operation is \(S[i]\)) can be satisfied. Let’s say there are \(k\) vertices adjacent to \(i\) other than the parent \(p_i\), and their colors have already been determined. If \(i\) is the root, the constraint requires that \(k\) is odd, and we just need to check if more than half of these vertices \(j\) satisfy \(T[j] = S[i]\).

If \(i\) is not the root, the constraint requires that \(k\) is even, and among these vertices \(j\), if the number of those satisfying \(T[j] = S[i]\) is:

• strictly greater than \(\displaystyle\frac{k}{2}\), the condition for \(i\) is satisfied regardless of whether \(T[p_i]\) is determined as B or W;

• exactly \(\displaystyle\frac{k}{2}\), we need to determine \(T[p_i] = S[i]\) to satisfy the condition for \(i\);

• strictly less than \(\displaystyle\frac{k}{2}\), the condition for \(i\) cannot be satisfied regardless of whether \(T[p_i]\) is determined as B or W.

In particular, if \(i\) is a leaf, then \(k = 0\), and the color \(T[p_i]\) of the parent \(p_i\) is completely determined.

In the process of determining the color before the operation from the leaves to the root, combined with the following “When the color before the operation is undetermined”, if a violation occurs at the root, the third state occurs at a vertex other than the root, or the second state occurs at a vertex \(p_i\) where it has already been concluded that “it is necessary to determine \(T[p_i] \neq S[i]\),” there is no suitable color sequence as \(T\). If none of these events occur, the desired color sequence \(T\) has been obtained as a result.

When the color before the operation is undetermined

Let’s say that for vertex \(i\), the color before the operation \(T[i]\) was not determined by the conditions for the children. In this case, if vertex \(i\) is the root, we can determine \(T[i]\) as either B or W. Also, if vertex \(i\) is not the root, we can determine \(T[i] = S[p_i]\) with \(p_i\) being the parent. To ensure this, we need to confirm that if a solution can be obtained by determining \(T[i] \neq S[p_i]\), a solution can also be obtained by determining \(T[i] = S[p_i]\) (i.e., we do not lose anything).

Suppose that by determining \(T[i] \neq S[p_i]\) and repeating the same procedure, we obtain the desired solution \(T\). In this case, the color sequence obtained by changing only \(T[i]\) to \(S[p_i]\) is also a solution. This is because the only vertices affected by changing the color of \(T[i]\) are those adjacent to \(i\), and for the children of \(i\), the conditions were satisfied before determining \(T[i]\), and for \(p_i\), even if \(T[i]\) was not \(S[p_i]\), it is \(S[p_i]\) after the operation, so the result does not change even if \(T[i]\) is changed to \(S[p_i]\).

Sample Implementation (C, 67 ms)

(Above is a modification of a translation by GPT-4.)