各頂点を parity で白黒に塗っておくことにする．

根付き森があったときに，これを消せる条件というのを考える． （根方向からは消せないものとする）

各部分木 \(t\) に対して \(3\) つの値を求める．

• \(white(t)\): 白の頂点数
• \(black(t)\): 黒の頂点数
• \(best(t)\): この部分木をどれだけ小さくできるか

\(best(t)\) は次のように定義する． \(t\) + 無限の孤立黒頂点 + 無限の孤立白頂点 があったとき，この \(t\) を消すような操作を考える． ここで，この \(t\) 内の \(2\) 頂点を選ぶような操作が多いと以降の操作で嬉しそうだと思ってみる． そこで，この「\(t\) 内の頂点 + 孤立頂点」で操作した回数を最小化し，この最小値を \(best(t)\) とおく．

ここで，\(best(t)\) には次の性質がある．

• 任意の \(c=best(t),best(t)+2,\cdots,white(t)+black(t)\) について，「\(t\) 内の頂点 + 孤立頂点」で操作した回数がちょうど \(c\) 回であるような操作列が存在する．
• さらに，上記のような操作列であって，次の形であるものが必ず存在する．
  • 一般性を失わず，部分木の根が黒色だとする．
  • \(a=max(white(t)-black(t),0), b=max(black(t)-white(t),0)\) と定義する．
  • 「\(t\) 内の頂点 + 孤立頂点」という操作で \(t\) 側から選んだ頂点の色の列が，白\(\times a+\)黒\(\times b+\)白黒白黒\(\cdots\) (全体の長さが \(c\)) となる．（部分木の根が白だったら，最後が黒白\(\cdots\)になる）

この性質を使うことで，部分木のマージ関数が書けるようになり，各部分木に対する \(best(t)\) を木 DP で求めることができる． また，マージの様子を考えることで上記の性質が成立することも確認できる．

次に，根付き木 \(t_1,t_2,\cdots\) があったときにこれらを消せる条件を考える．

• \(white(t_i)\) の総和と \(black(t_i)\) の総和が等しい
• 根が白い木と根が黒い木が存在
• どの根付き木 \(t_i\) についても，\(best(t_i) \leq \) それ以外の木の頂点数の和

が明らかに必要．そしてこれは十分でもある． \(best(t_i)\) の性質を用いることで適切な操作列が作成できるためである．

以上の議論を前提に，数え上げを DP で解く．

最終的に削る根付き部分木の集合を考える． この中で \(best\) が最大になるものを固定し，部分木 \(v-p\) （頂点 \(v\) の親が \(p\) になるようにしたとき，\(v\) を根とする部分木）とおく．

あとは部分木 \(p-v\) 内で部分木の集合を適当にとって上の条件を満たす方法が何通りあるか数えれば良い．

これは素直に DP すると，各部分木について使った \(white,black\) の頂点数をキーにしたテーブルを求めればよいことになる．

計算量が全体で \(O(N^5)\) になってしまうが，様々な部分で定数が軽いので十分高速になる．（\(white \times black\) が小さい，部分木 \(p-v\) のサイズが平均して小さい等）

実装例