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 2
1 3 | 1 |
5
1 2
2 3
3 4
3 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