Solução escrita por Enzo Dantas e Caique Paiva
Um emparelhamento é um conjunto de arestas onde cada vértice tem grau 1 ou 0. Dada uma árvore com $$n$$ vértices, qual é o maior número de arestas em um emparelhamento?
Input
A primeira linha tem um inteiro $$n$$: O número de vértices. Os vértices são numerados em $$1, 2, 3, \cdots, n$$.
Então, temos $$n-1$$ linhas descrevendo as arestas. Cada linha tem dois inteiros $$a, b$$: tem uma aresta de $$a$$ para $$b$$.
Output
Imprima um inteiro: a quantidade máxima de pares.
Constantes
$$1 \le n \le 2 \cdot 10^5$$
$$1 \le a, b \le n$$
| Entrada | Saída |
5 1 2 1 3 3 4 3 5 |
2 |
Explicação: O maior emparelhamento possível é $$(1, 2)$$ e $$(3, 4)$$.
(Link para submeter o problema).
[spoiler title=’Dica’ style=’purple’ collapse_link=’true’]Olhe para as folhas do grafo.[/spoiler]
[spoiler title=’Solução’ style=’blue’ collapse_link=’true’]
Solução gulosa:
Perceba que não faz sentido deixar uma folha e seu pai despareados, a não ser que o pai esteja pareado com outra folha. Assim, começando pelas folhas e subindo, podemos escolher gulosamente um vértice não pareado com nenhum de seus filhos e pareá-lo com um deles caso ambos estejam despareados.
Segue o código para melhor entendimento
[/spoiler]