全方位木 DP を使わなくても、以下のようにして、最大マッチングに必要ない頂点を特定できます。

• 最大マッチングをひとつ構成する。他の解説にもある通り、これは葉から貪欲にマッチングすればよい。
• 最大マッチングに使っていない頂点から始めて、使われていない辺と使われている辺を交互に辿れるようなパスを考え、パスに使われている辺をマークする。
• 各頂点について、次の二つの条件のどちらかを満たせば、それは必要ない頂点である。
  • 現在の最大マッチングで使われていない。
  • 現在の最大マッチングで、親と接続する辺が使われており、その辺はマークされている。

辺のマークは、マッチングの増大路に対応します。また、構成されているマッチングの性質を考えると、根方向に進んでいく増大路は貪欲法に矛盾するため、2 つ目の操作は、開始する頂点の親から葉の方向への単純な DFS で実現できます。

以上で、\(O(N)\) でこの問題が解けました。