Привет codeforces!

Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?

Может быть алгоритм Куна? :)

Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.

Пусть $$$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_{even} \leq sz_{odd}$$$ верно, что $$$sz_{odd} = sz_{even}$$$ равносильно наличию полного паросочетания в лесе.

Спасибо за прочтение!