Hello codeforces!

What is the easiest way to check if there is a perfect pairing 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 complete pairing.

Let $sz_v$ be the subtree size of the $v$th vertex. Then I claim that there is a perfect pairing 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 pairing 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 pairing 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.

Thus $sz_{odd} = sz_{even}$ is equivalent to having a complete pairing.

Thanks for reading!