Максимальное паросочетание дерева
Задача
Вам дано дерево (связный ациклический неориентированный граф), состоящее из n вершин.
Найдите размер его максимального паросочетания (набор попарно несмежных ребер).
Входные данные:
В первой строке дано число n - количество вершин в дереве.
Далее идет n-1 строка, в каждой из которых дается по два числа a
i и b
i (1 <= a
i, b
i <= n) - ребра дерева.
Выходные данные:
Выведите одно число - размер максимального паросочетания данного дерева.
Примеры:
| Входные данные |
Выходные данные |
4
1 2
2 3
3 4 |
2 |
Пояснение:
В максимальное паросочетание данного дерева будут входить ребра 1-2 и 3-4.