根を任意に決めて，根付き木と見なします． このとき，葉から根に向かって遡るように色を決めていくことで，この問題を \(\mathrm{O}(N)\) 時間で解くことができます．

以下では，答えとして求めたい「操作前の色の列」を \(T\) とします． また，文字列 \(R\) の \(i\) 文字目（色の列 \(R\) に関する頂点 \(i\) の色に対応する文字）を \(R[i]\) で表します．

操作後の色に関する条件

頂点 \(i\) に関する条件（操作後に頂点 \(i\) の色が \(S[i]\) となる）を満たせるかどうかを考えます． \(i\) に隣接する頂点のうち，親 \(p_i\) 以外のものが \(k\) 個あり，それらの色が既に決まっているとします． \(i\) が根である場合，制約から \(k\) は奇数であり，それらの頂点 \(j\) のうち \(T[j] = S[i]\) を満たすものが過半数あるかどうかを確認すればよいです．

\(i\) が根でない場合，制約から \(k\) は偶数であり，それらの頂点 \(j\) のうち \(T[j] = S[i]\) を満たすものが

• \(\displaystyle\frac{k}{2}\) 個より真に多いとき，\(T[p_i]\) を B, W のどちらに決めても \(i\) に関する条件は満たされます．

• \(\displaystyle\frac{k}{2}\) 個ちょうどのとき，\(i\) に関する条件を満たすためには \(T[p_i] = S[i]\) と決める必要があります．

• \(\displaystyle\frac{k}{2}\) 個より真に少ないとき，\(T[p_i]\) を B, W のどちらに決めても \(i\) に関する条件は満たされません．

特に，\(i\) が葉の場合は \(k = 0\) であり，親 \(p_i\) の色 \(T[p_i]\) が全て決まります．

以下の「操作前の色が未定の場合」と組み合わせて葉から根に向かって操作前の色を決めていく過程で，根で条件違反が起こるか，根以外で \(3\) 番目の状態が起こるか，根以外で \(2\) 番目の状態が「既に \(T[p_i] \neq S[i]\) と決める必要があると結論付けられた」頂点 \(p_i\) で起こると，\(T\) として相応しい色の列は存在しません． そのようなことが一度も起こらなければ，結果として所望の色の列 \(T\) が得られています．

操作前の色が未定の場合

頂点 \(i\) について，操作前の色 \(T[i]\) が子に関する条件で決まらなかったとします． このとき，頂点 \(i\) が根であれば \(T[i]\) は B, W のどちらに決めてもよいです． また，頂点 \(i\) が根でなければ，親を \(p_i\) として \(T[i] = S[p_i]\) と決めてよいです． これを保証するには，\(T[i] \neq S[p_i]\) と決めて解が得られるなら，\(T[i] = S[p_i]\) と決めても解が得られる（損をしない）ことを確認すればよいです．

\(T[i] \neq S[p_i]\) と決めて同様の手順を繰り返した結果，所望の解 \(T\) が得られたとします． このとき，\(T[i]\) のみを \(S[p_i]\) で塗り替えて得られる色の列も解になっています． なぜなら，\(T[i]\) の色を変えることで影響を受けるのは \(i\) に隣接する頂点のみで，\(i\) の子に関しては \(T[i]\) を決める前に条件を満たしており，\(p_i\) に関しては「 \(T[i]\) が \(S[p_i]\) でなかったとしても操作後に \(S[p_i]\) である」ため，\(T[i]\) を \(S[p_i]\) に塗り替えても結果は変わらないからです．

実装例 (C, 67 ms)