Module: hash


Problem

8 /8


Búnkeres

Theory Click to read/hide

También hay varias formas de hacer hash eficiente de árboles enraizados. 
Uno de estos métodos se organiza de la siguiente manera:
Procesamos los vértices recursivamente, en orden de recorrido en profundidad. Supondremos que el hash de un solo vértice es igual a p. Para los vértices con hijos, primero ejecutamos el algoritmo para ellos, luego, a través de los hijos, calcularemos el hash del subárbol actual. Para hacer esto, considere los hash de subárboles de niños como una secuencia de números y calcule el hash a partir de esta secuencia. Este será el hash del subárbol actual.
Si el orden de los hijos no es importante para nosotros, entonces, antes de calcular el hash, clasificamos la secuencia de hash de los subárboles secundarios y luego calculamos el hash de la secuencia ordenada.

De esta manera, puede verificar el isomorfismo de los árboles: solo cuente el hash sin orden en los niños (es decir, cada vez que clasifique los hash de los niños). Y si los valores hash de las raíces coinciden, entonces los árboles son isomorfos, de lo contrario no.

Para árboles sin raíz, todo sucede de manera similar, pero el centroide debe tomarse como la raíz. O considere un par de hashes si hay dos centroides.

Problem

Petya y Vasya juegan con entusiasmo a los espías. Hoy están planificando dónde estarán 
localizó sus búnkeres secretos y sus cuarteles generales. 

Hasta ahora, Petya y Vasya han decidido que necesitarán exactamente n búnkeres, que se numerarán del 1 al n para mantener el secreto. 
Algunos de ellos estarán conectados por túneles de dos sentidos, y para mayor confiabilidad y secreto, los túneles serán accesibles desde cualquier búnker hacia cualquier sentido.
Petya y Vasya incluso decidieron cuál de los búnkeres estará conectado por túneles, pero no pueden elegir cuál será el cuartel general. 
Los muchachos quieren elegirlo y dividir los bunkers restantes entre ellos para obtener el mismo número de bunkers.Exactamente dos túneles conducen a la sede: uno del bunker que pertenece a Vasya, el otro del bunker que pertenece a Petya. 
                                                                                   
Cansado Petya fue a su casa, y por la mañana Vasya le mostró un plano en el que los búnkeres estaban marcados con puntos y los túneles con segmentos. 
Además, Vasya eligió el cuartel general de tal manera que el plano que dibujó fuera simétrico con respecto a una línea recta que pasa por el punto que corresponde al cuartel general.
 
Aunque Petya casi de inmediato le mostró a Vasya que había cometido un error y no dibujó la mitad de los búnkeres, se preguntó si era posible elegir un cuartel general y dibujar un plano tan simétrico.

Entrada:
La primera línea del archivo de entrada contiene un único número entero n (1 <= n <= 105) - el número de contenedores. 
Las siguientes n - 1 líneas contienen dos números enteros ui y vi (1 <= ui, vi <= n, ui ≠ vi) - número de bunkers conectados por el i-ésimo túnel. 
Se garantiza que solo hay un camino entre dos bunkers.

Salida:
En el archivo de salida, imprima "SÍ" si es posible elegir una sede y dibujar dicho plan, o "NO" si eso no es posible.

Ejemplos:
 

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!

Entrada Salida
2
1 2 		NO
3
1 2
2 3 		SI