Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребромРазрешить выбирать ребро из корня к ребенку* Не занимать корень ребрамиЗапретить выбирать ребра из корня
В первом случае мы не сможем рассматривать его детей вовсе. В ином случае мы переходим в его поддеревья и выполняем то же самое действие.Если мы оставляем корень свободнымзапрещаем, значит можем разрешить всем его детям иметь в своих поддеревьях занятый кореньвыбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые уже не заняты были выбраны ребром из корня.
===Рекуррентная формула===
