Corrispondenza massima dell'albero
Problem
Ti viene dato un albero (un grafo non orientato aciclico connesso) costituito da n vertici.
Trova la dimensione della sua corrispondenza massima (l'insieme di bordi non adiacenti a coppie).
Inserimento:
La prima riga contiene il numero n - il numero di vertici nell'albero.
Seguono n-1 righe, ognuna delle quali contiene due numeri a
i e b
i (1 <= a
i, b
i >i <= n) - bordi dell'albero.
Uscita:
Stampa un numero - la dimensione della corrispondenza massima dell'albero dato.
Esempi:
| Input |
Uscita |
4
1 2
23
3 4 |
2 |
Spiegazione:
La corrispondenza massima di questo albero includerà i bordi 1-2 e 3-4.