Привет 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}$$$ равносильно наличию полного паросочетания в лесе.
Спасибо за прочтение!
Автокомментарий: текст был обновлен пользователем PvPro (предыдущая версия, новая версия, сравнить).
Прикольный факт. По факту совершенное паросочетание строится путём разбиения на пары вершин с нечётным размером поддерева и их родителей
Auto comment: topic has been translated by PvPro (original revision, translated revision, compare)
Auto comment: topic has been updated by PvPro (previous revision, new revision, compare).
Very nice idea. I have attempted to repackage the ideas of the proof into a more colloquial explanation. Note I will use “odd/even vertex” to mean a vertex with an odd/even sized subtree.
There are two key observations: every odd vertex must be matched with its parent, and every even vertex has at least one odd child. So to construct a perfect matching, we must match every even vertex to one of its odd children. If |{odd vertices}| = |{even vertices}|, we have found a perfect matching. Else the matching cannot be completed as the only unmatched vertices are odd, and odd vertices cannot be matched to each other because every odd vertex must be matched with its parent.
I have seen and self derived a generalisation of this lemma a few times. Details:
Lemma: Let k be an integer and G be a tree of size n. Suppose n is divisible by k, then we can split G into exactly (n/k) connected components of equal size, iff there are (n/k) subtree sizes that are divisble k.
Proposition: The number of subtree sizes are always $$$\leq n/k$$$.
Proof of lemma: If we just make cuts from every such subtree, then every commponent would have size multiple of $$$k$$$. But we have $$$n/k$$$ such components and they are not empty, so each of them must be size $$$k$$$.
Conversely, the subtree of LCA of any given component must always be written as a disjoint unions of components. THese give (n/k) vertices whose subtrees sizes divisible by $$$k$$$.
Proof of Proposition: For a direct proof: Use strong induction on the following statement instead: The number of such subtree are at most $$$\leq n/k$$$, but we do not require $$$n$$$ to be divisble by $$$k$$$. Alternatively, through the proof of previous lemma, we gets more than n/k nonempty components, each of size divisble by $$$k$$$. This is a contradiction.
Edit: thanks for pointing out missing defintion of k
This generalization (I assume that
kis the target size of each of the connected component) is the statement of 2011 Polish ICPC (AMPPZ) problem "Jaskinia" ("Cave"). The only difference is that in this problem, for a given tree you must identify alln/ks that will work (and output them in an increasing order).Also, worth mentioning that following simple greedy is both useful and instructive. It should not be overlooked:
Process all leafs one by one, commit to match it with its parents. If the parent was already matched, that this leaf will be discraded.
This also correctly find the maximum matching.
Intuitive Proof: A leaf can only be matched with its parent or be discraded. If you match it with its parent, you get a profit (in matching number) of 1. If you discard it, then the only thing you gain is free-ing up the parent, but having a free parent clearly worth at most 1. This shows (Guaranteed Profit) >= (Maximum Potential Cost), so you can assume you always do it.
This is written in response to the first part of the article where you suggested Kuhn's algorithm.