頂点と辺にラベルがついている場合の判定問題について考えます。最後に残る頂点に 1 のラベルがついているようにできる場合、 よい木 であるということにします。

\(N=1\) の場合は明らかです。それ以外の場合を考えます。

葉に 1 というラベルがついており、その葉に接続する辺に OR というラベルがついていた場合、この辺を最後に操作することで最後に残る頂点についているラベルが 1 にすることができるため、これはよい木です。

以降は与えられる木にそのような箇所が存在しないことを仮定します。このとき、以下の \(3\) つの事実が重要です。

• 葉に 0 というラベルがついており、その葉に接続する辺に AND というラベルがついていた場合、この辺をいつ操作したとしても、この葉に接続した頂点のラベルが \(0\) に書き換えられます。この辺に対して操作を行ったあとの木がよい木であるならば、もとの木もよい木です。

• 葉に 0 というラベルがついており、その葉に接続する辺に OR というラベルがついていた場合、この辺をいつ操作したとしても、この葉に接続した頂点のラベルが変化することはありません。この辺に対して操作を行ったあとの木がよい木であるならば、もとの木もよい木です。

• 葉に 1 というラベルがついており、その葉に接続する辺に AND というラベルがついていた場合、この辺をいつ操作したとしても、この葉に接続した頂点のラベルが変化することはありません。この辺に対して操作を行ったあとの木がよい木であるならば、もとの木もよい木です。

以上のことから葉に着目して貪欲に操作を実行しつづければよいことがわかります。これで判定問題を解くことができました。以降は数え上げることを考えます。

頂点 \(1\) を根とする根つき木とします。頂点 \(i\) の部分木以下に対して操作を行うことを考えます。このとき、操作の過程で 1-OR という葉が現れたなら他の部分がどのようなラベルづけであったとしてもよい木です。現れなかったなら、頂点 \(i\) の子孫は全て操作によって削除することができます。つまり、頂点 \(i\) の子孫たちに対してさきほどの貪欲法に従って操作したとき、以下の \(3\) つの状態のいずれかになることがわかります。

• よい木であることが確定する
• 0 が頂点 \(i\) に書き込まれる
• 1 が頂点 \(i\) に書き込まれる

この \(3\) つの状態を持って、DPを行うことで \(O(N)\) でこの問題を解くことができます。これは十分高速に動作します。