Problem
Tienes un árbol (un gráfico no dirigido acíclico conectado) que consta de n vértices.
Encuentre el tamaño de su coincidencia máxima (el conjunto de aristas no adyacentes por pares).
Entrada:
La primera línea contiene el número n - el número de vértices en el árbol.
Luego vienen n-1 líneas, cada una de las cuales contiene dos números a
i y b
i (1 <= a
i, b
i <= n) - bordes del árbol.
Salida:
Imprima un número: el tamaño de la coincidencia máxima del árbol dado.
Ejemplos:
| Entrada |
Salida |
4
1 2
23
3 4 |
2 |
Explicación:
La coincidencia máxima de este árbol incluirá los bordes 1-2 y 3-4.