Processing math: 100%

Совершенное паросочетание в дереве

Revision ru3, by PvPro, 2024-12-02 00:48:37

Привет codeforces!

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

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

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

Пусть szv — размер поддерева v-й вершины. Тогда я утверждаю, что совершенное паросочетание есть тогда и только тогда, когда ровно половина всех szv четная.

Доказательство:

Пусть szodd — количество нечетных поддеревьев, а szeven — количетво четных поддеревьев.

Сначала докажем, что szevenszodd.

Заметим, что szv=uszu+1 (u — ребенок v). Если szv четно, то хотя-бы один из детей u имеет нечетный размер поддерева, потому что их сумма нечетная. Сопоставим в пару каждому четному szv нечетное szu (u — ребенок v). Таким образом szevenszodd. Более того, мы доказали, что если szeven=szodd, то в дереве есть совершенное паросочетание, явно выбрав каждому четному szv пару.

Теперь докажем, что если szevenszodd, то в дереве нет полного паросочетания. Допустим есть. Тогда в нем есть ребро, соединяющее v,u, такие что szvszu1 (mod 2). Пусть v — родитель u. Тогда заметим, что каждое ребро либо целиком содержится в поддереве v, либо нет. В обоих случаях ребро забирает из поддерева v четное количество вершин, а значит и суммарно они заберут четное количество вершин, но szv1 (mod 2) — противоречие.

Более того из-за неравенства szevenszodd верно, что szodd=szeven равносильно наличию полного паросочетания в лесе.

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

Tags matching, tree

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 Первая редакция (сохранено в черновиках)