Задача

2 /7


Максимальное паросочетание дерева

Задача

Вам дано дерево (связный ациклический неориентированный граф), состоящее из n вершин.
Найдите размер его максимального паросочетания (набор попарно несмежных ребер).

Входные данные:
В первой строке дано число n - количество вершин в дереве.
Далее идет n-1 строка, в каждой из которых дается по два числа ai и bi (1 <= ai, bi <= n) - ребра дерева.

Выходные данные:
Выведите одно число - размер максимального паросочетания данного дерева.

Примеры:
 
Входные данные Выходные данные
4
1 2
2 3
3 4
2

Пояснение:
В максимальное паросочетание данного дерева будут входить ребра 1-2 и 3-4.


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Mingw-w644
Комментарий учителя