Trova il centroide di un albero
Ti viene fornito un albero con v vertici e il tuo compito è trovare il centroide dell’albero. Il centroide di un albero è un vertice tale che, quando viene rimosso, tutti i sottoalberi rimanenti hanno una dimensione di al massimo nodi.
Ingresso
La prima riga dell’input contiene un singolo intero v (1 ≤ v ≤ 100 000).
Le successive v-1 righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che significano che il vertice v1 è collegato al vertice v2 e viceversa.
Uscita
Il programma deve stampare il centroide dell’albero fornito. Se ci sono più risposte possibili, è sufficiente stamparne una qualunque.
Esempi
Ingresso | Uscita |
|---|---|
3 | 1 |
5 | 3 |
Suggerimento
Puoi calcolare la dimensione del sottoalbero di ogni nodo (cioè il numero di nodi figli).
Poi, per ciascun nodo, verifica se la dimensione dei suoi sottoalberi è minore o uguale alla metà dei vertici nell’intero albero (tutti i nodi figli e v-currentNodeSize per considerare il sottoalbero del genitore).
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB