Hello codeforces!↵
↵
What is the easiest way to check if there is a perfect pairing in the tree?↵
↵
Maybe [Kuhn's algorithm](https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Куна_для_поиска_максимального_паросочетанияcp-algorithms.com/graph/kuhn_maximum_bipartite_matching.html)? :)↵
↵
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!↵
↵
What is the easiest way to check if there is a perfect pairing in the tree?↵
↵
Maybe [Kuhn's algorithm](https://
↵
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!↵
