Hello codeforces!

What is the easiest way to check if there is a perfect matching in the tree?

Maybe Kuhn's algorithm? :)

Most likely you are thinking about dynamics on subtrees. This is indeed a good way, because it works for the size of the input. However, there is an easier way to check if a tree has a perfect matching.

Let $$$sz_v$$$ be the subtree size of the $$$v$$$th vertex. Then I claim that there is a perfect matching iff exactly half of all $$$sz_v$$$ are even.

Proof:

Let $$$sz_{odd}$$$ be the number of odd subtrees, and $$$sz_{even}$$$ be the number of even subtrees.

We first prove that $$$sz_{even} \leq sz_{odd}$$$.

Note that $$$sz_v = \sum_{u}^{} sz_u + 1$$$ ($$$u$$$ — child of $$$v$$$). If $$$sz_v$$$ is even, then at least one of the children of $$$u$$$ has an odd subtree size, because their sum is odd. We pair each even $$$sz_v$$$ with an odd $$$sz_u$$$ ($$$u$$$ — child $$$v$$$). Thus $$$sz_{even} \leq sz_{odd}$$$. Moreover, we proved that if $$$sz_{even} = sz_{odd}$$$, then there is a perfect matchingg in the tree by explicitly choosing every even $$$sz_v$$$ to be a pair.

Now we prove that if $$$sz_{even} \neq sz_{odd}$$$, then there is no perfect matching in the tree. Suppose there is. Then it has an edge connecting $$$v, u$$$ such that $$$sz_v \equiv sz_u \equiv 1\space (mod\space 2)$$$. Let $$$v$$$ — be the parent of $$$u$$$. Then note that each edge is either entirely contained in a subtree of $$$v$$$ or not. In both cases, the edge takes an even number of vertices from subtree $$$v$$$, and hence they will also take an even number of vertices in total, but $$$sz_v \equiv 1\space(mod\space 2)$$$ — contradiction.

Furthermore, because of the inequality $$$sz_{even} \leq sz_{odd}$$$ it is true that $$$sz_{odd} = sz_{even}$$$ is equivalent to the presence of a perfect matching in the forest.

Thanks for reading!