Module: Hash


Problem

8 /8


Bunkers

Theory Click to read/hide

Existem também várias maneiras de fazer hash de árvores enraizadas com eficiência. 
Um desses métodos é organizado da seguinte forma:
Processamos os vértices recursivamente, em ordem de travessia em profundidade. Assumiremos que o hash de um único vértice é igual a p. Para vértices com filhos, primeiro executamos o algoritmo para eles e, a partir dos filhos, calculamos o hash da subárvore atual. Para fazer isso, considere os hashes das subárvores dos filhos como uma sequência de números e calcule o hash a partir dessa sequência. Este será o hash da subárvore atual.
Se a ordem dos filhos não for importante para nós, antes de calcular o hash, classificamos a sequência de hashes das subárvores filhas e, em seguida, calculamos o hash da sequência classificada.

Dessa forma, você pode verificar o isomorfismo das árvores - basta contar o hash sem ordem nos filhos (ou seja, cada vez classificando os hashes dos filhos). E se os hashes das raízes coincidirem, então as árvores são isomórficas, caso contrário não.

Para árvores não enraizadas, tudo acontece de maneira semelhante, mas o centróide deve ser considerado a raiz. Ou considere um par de hashes se houver dois centróides.

Problem

Petya e Vasya brincam de espiões com entusiasmo. Hoje eles estão planejando onde estarão 
localizaram seus bunkers e quartéis-generais secretos. 

Até agora, Petya e Vasya decidiram que precisarão de exatamente n bunkers, que serão numerados de 1 a n para sigilo. 
Alguns deles serão conectados por túneis de mão dupla e, para confiabilidade e sigilo, os túneis serão acessíveis de qualquer bunker para qualquer caminho.
Petya e Vasya até decidiram qual dos bunkers será conectado por túneis, mas não podem escolher qual deles será o quartel-general. 
Os meninos querem escolhê-lo e dividir os bunkers restantes entre si para obter um número igual de bunkers. Exatamente dois túneis levam ao quartel-general: um do bunker pertencente a Vasya, outro do bunker pertencente a Petya. 
                                                                                   
Cansado, Petya foi para sua casa e, pela manhã, Vasya mostrou-lhe um plano no qual os bunkers eram marcados com pontos e os túneis com segmentos. 
Além disso, Vasya escolheu o quartel-general de forma que o plano que ele desenhou fosse simétrico em relação a uma linha reta passando pelo ponto que correspondia ao quartel-general.
 
Embora Petya quase imediatamente tenha mostrado a Vasya que havia cometido um erro e não desenhado metade dos bunkers, ele se perguntou se seria possível escolher um quartel-general e desenhar um plano tão simétrico.

Entrada:
A primeira linha do arquivo de entrada contém um único inteiro n (1 <= n <= 105) - o número de compartimentos. 
As próximas n - 1 linhas contêm dois inteiros ui e vi (1 <= ui, vi <= n, ui ≠ vi) - número de bunkers conectados pelo i-ésimo túnel. 
É garantido que existe apenas um caminho entre quaisquer dois bunkers.

Saída:
No arquivo de saída imprima "SIM" se for possível escolher uma sede e traçar tal plano, ou "NÃO" se isso não for possível.

Exemplos:
 
Entrada Saída
2
1 2 		NÃO
3
1 2
2 3 		SIM

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!