Colorazione dell'albero#11002
Vi è dato un albero (un grafo non orientato, connesso e aciclico) composto da vertici. Giocate a un gioco su questo albero.
Inizialmente tutti i vertici sono colorati di bianco. Alla prima mossa scegliete un vertice e lo colorate di nero. Successivamente, a ogni mossa, scegliete un vertice bianco adiacente (cioè collegato da un arco) ad almeno un vertice nero e lo colorate di nero.
Ogni volta che scegliete un vertice (compresa la prima mossa), ottenete un numero di punti pari alla dimensione della componente connessa composta esclusivamente da vertici bianchi e contenente il vertice scelto. Il gioco termina quando tutti i vertici diventano neri.
Consideriamo il seguente esempio:
I vertici e sono già colorati di nero. Se scegliete il vertice , otterrete punti per la componente connessa costituita dai vertici e . Se scegliete il vertice , otterrete punti per la componente connessa costituita dai vertici e .
Il vostro compito è massimizzare il numero totale di punti che potete ottenere.
La prima riga contiene un numero intero n~(2 \le n \le 2 \cdot 10^5) — il numero di vertici dell'albero.
Ciascuna delle successive n - 1 righe descrive un arco dell'albero. L'arco è definito da due numeri interi u_i e v_i~(1 \le u_i, v_i \le n,\ u_i \ne v_i) — i numeri dei vertici che esso collega.
È garantito che gli archi forniti formano un albero.
Stampate un numero intero — il numero massimo di punti che potete ottenere giocando in modo ottimale.
Esempio 1
Esempio 2