Correspondência Máxima de Árvore
Problem
Você recebe uma árvore (um grafo não direcionado acíclico conectado) que consiste em n vértices.
Encontre o tamanho de sua correspondência máxima (o conjunto de arestas não adjacentes aos pares).
Entrada:
A primeira linha contém o número n - o número de vértices na árvore.
A seguir vem n-1 linhas, cada uma contendo dois números a
i e b
i (1 <= a
i, b
i <= n) - arestas de árvores.
Saída:
Imprima um número - o tamanho da correspondência máxima da árvore fornecida.
Exemplos:
| Entrada |
Saída |
4
1 2
23
3 4 |
2 |
Explicação:
A correspondência máxima dessa árvore incluirá as arestas 1-2 e 3-4.