Module: Hachage


Problem

8 /8


Soutes

Theory Click to read/hide

Il existe également plusieurs façons de hacher efficacement les arbres enracinés. 
L'une de ces méthodes est organisée comme suit :
Nous traitons les sommets de manière récursive, dans l'ordre de parcours en profondeur. Nous supposerons que le hachage d'un seul sommet est égal à p. Pour les sommets avec des enfants, nous exécutons d'abord l'algorithme pour eux, puis à travers les enfants, nous calculerons le hachage du sous-arbre actuel. Pour ce faire, considérez les hachages des sous-arbres d'enfants comme une séquence de nombres et calculez le hachage à partir de cette séquence. Ce sera le hachage du sous-arbre actuel.
Si l'ordre des enfants n'est pas important pour nous, alors avant de calculer le hachage, nous trions la séquence de hachages des sous-arbres enfants, puis calculons le hachage à partir de la séquence triée.

De cette façon, vous pouvez vérifier l'isomorphisme des arbres - il suffit de compter le hachage sans ordre sur les enfants (c'est-à-dire de trier à chaque fois les hachages des enfants). Et si les hachages des racines correspondent, alors les arbres sont isomorphes, sinon non.

Pour les arbres non enracinés, tout se passe de la même manière, mais le centroïde doit être pris comme racine. Ou considérez une paire de hachages s'il y a deux centroïdes.

Problem

Petya et Vasya jouent avec enthousiasme les espions. Aujourd'hui, ils planifient où ils seront 
ont localisé leurs bunkers secrets et leur quartier général. 

Jusqu'à présent, Petya et Vasya ont décidé qu'ils auraient besoin d'exactement n bunkers, qui seront numérotés de 1 à n pour le secret. 
Certains d'entre eux seront reliés par des tunnels bidirectionnels, et pour des raisons de fiabilité et de confidentialité, les tunnels seront accessibles depuis n'importe quel bunker vers n'importe quel sens.
Petya et Vasya ont même décidé lequel des bunkers sera relié par des tunnels, mais ils ne peuvent pas choisir lequel sera le quartier général. 
Les garçons veulent le choisir et se partagent les bunkers restants afin d'obtenir un nombre égal de bunkers. Exactement deux tunnels mènent au quartier général : l'un depuis le bunker appartenant à Vasya, l'autre depuis le bunker appartenant à Petya. 
                                                                                   
Fatigué, Petya se rendit chez lui et, le matin, Vasya lui montra un plan sur lequel les bunkers étaient marqués de points et les tunnels de segments. 
De plus, Vasya a choisi le quartier général de manière à ce que le plan qu'il a tracé soit symétrique par rapport à une droite passant par le point correspondant au quartier général.
 
Bien que Petya ait presque immédiatement montré à Vasya qu'il avait fait une erreur et qu'il n'avait pas dessiné la moitié des bunkers, il s'est demandé s'il était possible de choisir un quartier général et de dessiner un plan aussi symétrique.

Saisie :
La première ligne du fichier d'entrée contient un seul entier n (1 <= n <= 105) - le nombre de bacs. 
Les n - 1 lignes suivantes contiennent deux entiers ui et vi (1 <= ui, vi sub> <= n, ui ≠ vi) - nombre de bunkers reliés par le i-ème tunnel. 
Il est garanti qu'il n'y a qu'un seul chemin entre deux bunkers.

Sortie :
Dans le fichier de sortie écrivez "OUI" s'il est possible de choisir un quartier général et de dessiner un tel plan, ou "NON" si ce n'est pas possible.

Exemples :
 
Entrée Sortie
2
1 2 		NON
3
1 2
2 3 		OUI

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!