1 にできない木の条件を考える。

OR辺で切るとAND辺のみからなるいくつかの部分木（AND部分木 と呼ぶことにする）に分かれる。 これらのAND部分木が全て 0 を含む、というのが必要十分条件である。

必要性

0 を含まないAND部分木があれば、AND辺を全て縮約してからOR辺を全て縮約することにより 1 にできる。

十分性

どのような操作をしてもこの条件が保たれることを示す。

• AND辺の縮約：明らか
• OR辺の縮約：辺の両端のAND部分木をマージする形になるが、両方のAND部分木が 0 を含んでいることを考えると、マージ後のAND部分木には 1 個以上の 0 が含まれることが分かる

数え方

• \(dp[v][0/1] =\) v 以下の部分木を決めたとき、v が属するAND部分木にすでに 0 が含まれている/いない場合の数

おまけ

writer解説の箇条書きの１項目（AND-0）の正当性が非自明に感じたのでsigma425氏に聞いたところ理解を得られたので書いておきます。

ある辺を縮約してできる頂点は、元の木のある部分木を縮約したものである。
その部分木内の辺の操作順を変更しても、他の部分に影響はない。
AND/ORの性質を考えると 0 よりも 1 の方が真に良いことを考えると、ある部分木を縮約した結果が 0 ならばその部分木内の辺の順番を変更しても結果が悪くなることはなく、0 の葉がついたAND辺を最初に縮約しても良いことが言える。