最初の操作を辺 \(e_1\) に、次の操作を辺 \(e_2\) に行うとします。ほとんどの場合、この二辺の順番を入れ替えても（\(e_1 \rightarrow e_2\) の代わりに \(e_2 \rightarrow e_1\) としても）結果は同じで、mod \(2\) で打ち消し合います。唯一の例外は \(e_1\) と \(e_2\) が頂点を共有するときであり、したがって最初の二操作は隣接する辺に対して行われると仮定できます。

x --- y --- z という部分に二操作を行う方法は二通りあり、一方では NAND(NAND(y, x), z)、もう一方では NAND(NAND(y, z), x) が得られます。\(x = z\) の場合、両者は等しく、mod \(2\) で打ち消し合いますが、\(x \neq z\) の場合、両者は異なることが確認できます。

ここで鍵となる考察を行います。行える操作を次のものに変えても問題の答えは変わりません。操作: 頂点を選び、下図のように二辺を「吸収」させる。

  \       |      /                       \ | /
--- x --- y --- z ---        =>        --- x ---
  /       |      \                       / | \

ここで、操作を反対方向から行うことで \(z\) を得ることもできることに注意します。ここでも、\(x = z\) のとき、またそのときに限り二通りの操作方法は打ち消し合います。

では、改変後の問題を解きましょう。簡略化のため、はじめの木の辺数は偶数であるとします。ある頂点について、操作を終えたときにその頂点を「残す」方法が奇数通りであるとき、その頂点を 良い 頂点と呼びましょう。答えは、はじめに \(1\) が書き込まれている 良い 頂点の個数です。

ある頂点が 良い 頂点か否かはどう判定すればよいでしょうか。木に根を付け、根が 良い 頂点かを判定しましょう。根を対象としない操作は行わないとしてよく（そのような操作は二方向から可能であり、両者は打ち消し合います）、常に根を対象として操作を行う方法の個数は単純な木 DP により数えられます。この個数の偶奇が根付き木をトポロジカルソートする方法の個数と一致することも示せます（この考察により実装が簡略化されます）。

はじめの木の辺数が奇数である場合はどうすればよいでしょうか。最初の操作での辺の選択肢を全て試せば、偶数の場合に帰着します。