Задача AI-Masters.

Постройте алгоритм, который получает на вход дерево и за линейное время определяет, есть ли в нем совершенное паросочетание, то есть множество ребер, такое, что каждая вершина графа встречается ровно в одном ребре множества.

Решение:

Определение совершенного паросочетания дано в условии задачи.

Давайте подвесим дерево за вершину 1 и запустим dfs от этой вершины.
Стандартный dfs принимает два аргумента v, p - вершина в котором находимся и вершина от которой пришли в вершину v.
Но давайте еще передавать булеву переменную bool_took, которая равна true если вершина взята в паросочетание и false иначе.
Таким образом дфс выглядит следующим образом dfs(int v, int p, int bool_took), наша функция вернет true если поддерво вершины v при условии bool_took, можно сделать совершенным паросочетанием.

Вот мы вошли в функцию dfs, что мы должны сделать если bool_took = false и что мы должны сделать если bool_took = true ?

- Если bool_took = true нужно запустить dfs от всех детей вершины v с параметром bool_took = false и если все вызовы dfs вернули true то мы в свою очередь тоже можем вернуть true.

- Если bool_took = false нужно выбрать какого-то ребенка вершины v и взять их в паросочетание, пусть эта вершина u, тогда если dfs(u, v, true) вернул true и dfs(to, v, false) вернул true для всех детей to не равным u мы можем спокойно возвращать true.

Время работы алгоритма O(N).

Код с комментариями в описание.