Привет codeforces!
Какой самый простой способ проверить есть ли в дереве совершенное паросочетание?
Может быть алгоритм Куна? :)
Скорее всго вы подумали про динамику по поддеревьям. Действительно это хороший способ, ведь он работает за размер ввода. Однако есть более простой способ проверить имеет ли дерево полное паросочетание.
Пусть szv — размер поддерева v-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех szv четная.
Доказательство:
Пусть szodd — количество нечетных поддеревьев, а szeven — количетво четных поддеревьев.
Сначала докажем, что szeven≤szodd.
Заметим, что szv=∑uszu+1 (u — ребенок v). Если szv четно, то хотя-бы один из детей u имеет нечетный размер поддерева, потому что их сумма нечетная. Сопоставим в пару каждому четному szv нечетное szu (u — ребенок v). Таким образом szeven≤szodd. Более того, мы доказали, что если szeven=szodd, то в дереве есть совершенное паросочетание, явно выбрав каждому четному szv пару.
Теперь докажем, что если szeven≠szodd, то в дереве нет полного паросочетания. Допустим есть. Тогда в нем есть ребро, соединяющее v,u, такие что szv≡szu≡1 (mod 2). Пусть v — родитель u. Тогда заметим, что каждое ребро либо целиком содержится в поддереве v, либо нет. В обоих случаях ребро забирает из поддерева v четное количество вершин, а значит и суммарно они заберут четное количество вершин, но szv≡1 (mod 2) — противоречие.
Более того из-за неравенства szeven≤szodd верно, что szodd=szeven равносильно наличию полного паросочетания в лесе.
Спасибо за прочтение!