Trouver le centroïde d’un arbre
On vous donne un arbre composé de
v sommets, et votre objectif est de trouver le centroïde de cet arbre. Le centroïde d’un arbre est un sommet tel que, lorsqu’on le retire, tous les sous-arbres restants ont une taille d’au plus nœuds.Entrée
La première ligne de l’entrée contient un seul entier
v (1 ≤ v ≤ 100 000).Les
v-1 lignes suivantes contiennent des paires d’entiers v1, v2 (1 ≤ v1, v2 ≤ v), ce qui signifie que le sommet v1 est relié au sommet v2, et inversement.Sortie
Le programme doit afficher le centroïde de l’arbre donné. S’il existe plusieurs réponses possibles, le programme peut afficher n’importe laquelle.
Exemples
Entrée | Sortie |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Indice
Vous pouvez calculer la taille du sous-arbre pour chaque nœud (le nombre de nœuds enfants).
Ensuite, vérifiez pour tous les sous-arbres de chaque nœud si leur taille est inférieure ou égale à la moitié des sommets de l’ensemble de l’arbre (tous les nœuds enfants et
v - currentNodeSize pour tenir compte du sous-arbre parent).Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB