Привет codeforces!↵
↵
Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?↵
↵
Может быть [алгоритм Куна](https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Куна_для_поиска_максимального_паросочетания)? :)↵
↵
Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.↵
↵
Пусть $sz_v$ — размер поддерева $v$-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех $sz_v$ четная.↵
↵
Доказательство:↵
↵
Пусть $sz_{odd}$ — количество нечетных поддеревьев, а $sz_{even}$ — количетво четных поддеревьев.↵
↵
Сначала докажем, что $sz_{even} \leq sz_{odd}$.↵
↵
Заметим, что $sz_v = \sum_{u}^{} sz_u + 1$ ($u$ — ребенок $v$). Если $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$, такие что $sz_v \equiv sz_u \equiv 1\space (mod\space 2)$. Пусть $v$ — родитель $u$. Тогда заметим, что каждое ребро либо целиком содержится в поддереве $v$, либо нет. В обоих случаях ребро забирает из поддерева $v$ четное количество вершин, а значит и суммарно они заберут четное количество вершин, но $sz_v \equiv 1\space(mod\space 2)$ — противоречие.↵
↵
Таким образом $sz_{odd} = sz_{even}$ равносильно наличию полного паросочетания.↵
↵
Спасибо за прочтение!
↵
Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?↵
↵
Может быть [алгоритм Куна](https://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Куна_для_поиска_максимального_паросочетания)? :)↵
↵
Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.↵
↵
Пусть $sz_v$ — размер поддерева $v$-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех $sz_v$ четная.↵
↵
Доказательство:↵
↵
Пусть $sz_{odd}$ — количество нечетных поддеревьев, а $sz_{even}$ — количетво четных поддеревьев.↵
↵
Сначала докажем, что $sz_{even} \leq sz_{odd}$.↵
↵
Заметим, что $sz_v = \sum_{u}^{} sz_u + 1$ ($u$ — ребенок $v$). Если $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$, такие что $sz_v \equiv sz_u \equiv 1\space (mod\space 2)$. Пусть $v$ — родитель $u$. Тогда заметим, что каждое ребро либо целиком содержится в поддереве $v$, либо нет. В обоих случаях ребро забирает из поддерева $v$ четное количество вершин, а значит и суммарно они заберут четное количество вершин, но $sz_v \equiv 1\space(mod\space 2)$ — противоречие.↵
↵
Таким образом $sz_{odd} = sz_{even}$ равносильно наличию полного паросочетания.↵
↵
Спасибо за прочтение!
