Совершенное паросочетание в деревеPerfect matching in tree
Difference between ru2 and en1, changed 1,802 character(s)
Привет codeforces!↵
↵
Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?↵
↵
Может быть [алгоритм Куна](https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Куна_для_поиска_максимального_паросочетания)? :)↵
↵
Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.↵
↵
Пусть $sz_v$ — размер поддерева $v$-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех $sz_v$ четная.↵
↵
Доказательство:↵
↵
Пусть $sz_{odd}$ — количество нечетных поддеревьев, а $sz_{even}$ — количетво четных поддеревьев.↵
↵
Сначала докажем, что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=Алгоритм_Куна_для_поиска_максимального_паросочетания)? :)↵
↵
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$ четно, то хотя-бы один из детей $u$ имеет нечетный размер поддерева, потому что их сумма нечетная. Сопоставим в пару каждому четному $sz_v$ нечетное $sz_u$ ($u$ — ребенок $v$). Таким образом $sz_{even} \leq sz_{odd}$. Более того, мы доказали, что если $sz_{even} = sz_{odd}$, то в дереве есть совершенное паросочетание, явно выбрав каждому четному $sz_v$ пару.↵
↵
Теперь докажем, что если $sz_{even} \neq sz_{odd}$, то в дереве нет полного паросочетания. Допустим есть. Тогда в нем есть ребро, соединяющее $v, u$, такие что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$ — родитель $u$. Тогда заметим, что каждое ребро либо целиком содержится в поддереве $v$, либо нет. В обоих случаях ребро забирает из поддерева $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)$ — противоречие.↵
↵
Таким образом $sz_{odd} = sz_{even}$ равносильно наличию полного паросочетания.↵
↵
Спасибо за прочтение!contradiction.↵
↵
Thus $sz_{odd} = sz_{even}$ is equivalent to having a complete pairing.↵
↵
Thanks for reading!↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English PvPro 2024-12-02 00:52:42 1 Tiny change: 'sz_{even} {\leq sz_{o' -> 'sz_{even} \leq sz_{o'
en4 English PvPro 2024-12-02 00:52:29 175
ru3 Russian PvPro 2024-12-02 00:48:37 75
en3 English PvPro 2024-12-02 00:19:07 0 (published)
en2 English PvPro 2024-12-02 00:18:48 138 (saved to drafts)
en1 English PvPro 2024-12-02 00:15:26 1802 Initial revision for English translation
ru2 Russian PvPro 2024-12-02 00:07:38 0 (опубликовано)
ru1 Russian PvPro 2024-12-02 00:05:46 1907 Первая редакция (сохранено в черновиках)