Module: Hashing


Problem

8 /8


Bunker

Theory Click to read/hide

Esistono anche diversi modi per eseguire in modo efficiente l'hashing degli alberi radicati. 
Uno di questi metodi è organizzato come segue:
Elaboriamo i vertici in modo ricorsivo, in ordine di attraversamento in profondità. Supponiamo che l'hash di un singolo vertice sia uguale a p. Per i vertici con figli, prima eseguiamo l'algoritmo per loro, quindi attraverso i figli calcoleremo l'hash del sottoalbero corrente. Per fare ciò, considera gli hash dei sottoalberi dei figli come una sequenza di numeri e calcola l'hash da questa sequenza. Questo sarà l'hash del sottoalbero corrente.
Se l'ordine sui figli non è importante per noi, prima di calcolare l'hash, ordiniamo la sequenza di hash dai sottoalberi figli e quindi calcoliamo l'hash dalla sequenza ordinata.

In questo modo puoi controllare l'isomorfismo degli alberi: basta contare l'hash senza ordine sui figli (ovvero, ogni volta ordinando gli hash dei figli). E se gli hash delle radici corrispondono, allora gli alberi sono isomorfi, altrimenti no.

Per gli alberi senza radici, tutto avviene in modo simile, ma il baricentro deve essere preso come radice. Oppure considera una coppia di hash se ci sono due centroidi.

Problem

Petya e Vasya interpretano con entusiasmo le spie. Oggi stanno pianificando dove saranno 
localizzarono i loro bunker segreti e il loro quartier generale. 

Finora, Petya e Vasya hanno deciso che avranno bisogno esattamente di n bunker, che saranno numerati da 1 a n per la segretezza. 
Alcuni di essi saranno collegati da tunnel bidirezionali e, per affidabilità e segretezza, i tunnel saranno accessibili da qualsiasi bunker in qualsiasi direzione.
Petya e Vasya hanno persino deciso quale dei bunker sarà collegato da tunnel, ma non possono scegliere quale sarà il quartier generale. 
I ragazzi vogliono sceglierlo e dividere tra loro i bunker rimanenti in modo da ottenere un numero uguale di bunker Esattamente due tunnel conducono al quartier generale: uno dal bunker di Vasya, l'altro dal bunker di Petya. 
                                                                                   
Petya, stanco, andò a casa sua e al mattino Vasya gli mostrò una pianta in cui i bunker erano contrassegnati da punti e i tunnel da segmenti. 
Inoltre, Vasya scelse il quartier generale in modo tale che la pianta da lui disegnata fosse simmetrica rispetto a una linea retta passante per il punto che corrispondeva al quartier generale.
 
Sebbene Petya mostrò quasi immediatamente a Vasya di aver commesso un errore e di non aver disegnato metà dei bunker, si chiese se fosse possibile scegliere un quartier generale e disegnare un piano così simmetrico.

Inserimento:
La prima riga del file di input contiene un singolo numero intero n (1 <= n <= 105) - il numero di bin. 
Le successive n - 1 righe contengono due numeri interi ui e vi (1 <= ui, vi <= n, ui ≠ vi) - numero di bunker collegati dall'i-esimo tunnel. 
È garantito che esiste un solo percorso tra due bunker qualsiasi.

Uscita:
Nel file di output stampa "SI" se è possibile scegliere una sede e disegnare tale pianta, oppure "NO" se ciò non è possibile.

Esempi:
 
Input Uscita
2
1 2 		NO
3
1 2
2 3 		SÌ

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!