頂点 \(1\) を削除して得られるグラフの最大マッチングの大きさが元の木の最大マッチングの大きさと等しいか判定する方法を考えます。

頂点 \(1\) を根とし、最初全ての頂点は白色で塗られているとします。

以下の操作を各頂点 \(i\) について、頂点 \(1\) と頂点 \(i\) の距離が大きい方から順に行います。

頂点 \(i\) の子のうち白色で塗られている頂点があるとき、この \(2\) つをマッチングし、頂点 \(i\) を黒色で塗る。

元の木の最大マッチングの大きさは、この手順を行った時の最終的な黒色の頂点の個数に等しいことが証明できます。なお、この塗り分けは簡単な木DPで計算量 \(O(N)\) で実行できます。

このとき、頂点 \(1\) を削除して得られるグラフの最大マッチングの大きさが元の木の最大マッチングの大きさと等しいための条件は、頂点 \(1\) が白色で塗られていることです。ある頂点が問題文中の条件を満たすかの判定がその頂点を根とした \(O(N)\) の木DPで求められるので全方位木 DP を用いることでこの問題が \(O(N)\) で解けます。

全方位木DPに関しては以下の解説をご覧ください。

https://atcoder.jp/contests/abc222/editorial/2749