Arbres diferents P70214


Statement
 

pdf   zip

thehtml
Els professors d’Algorísmia ja no saben què fer perquè algú aprovi. Desesperats, en un examen teòric només van demanar que es dibuixés un arbre, a veure si d’aquesta manera...

Tres estudiants van fer això: El primer, que no sabia ni què se li preguntava, va dibuixar un arbre de la natura (en concret, un roure). Com a premi va obtenir una nota negativa.

El segon estudiant sí que va dibuixar el que calia, és a dir, un graf no dirigit, connex i acíclic. Malgrat els esforços dels professors per evitar còpies, el tercer estudiant va aconseguir veure l’arbre que havia dibuixat el segon estudiant. Això sí, després va haver de dibuixar un altre arbre que fos suficientment diferent, perquè el Roura no el suspengués per copiar.

Formalment, donat un arbre A amb vèrtexs 1, …, n, sigui gA(x) el grau (el nombre de veïns) del vèrtex x dins d’A. Diem que dos arbres A i B són suficientment diferents si, per a tota 1 ≤ x ≤ n, es compleix gA(x) ≠ gB(x).

Donat un arbre A amb n vèrtexs, existeix algun arbre B que també tingui n vèrtexs i que sigui suficientment diferent?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida d’n − 1 arestes x y. Suposeu 2 ≤ n ≤ 105, que els vèrtexs es numeren entre 1 i n, i que les arestes donades realment formen un arbre.

Sortida

Per a cada arbre donat, escriviu “SI” si existeix un arbre amb el mateix nombre de vèrtexs suficientment diferent, o “NO” altrament.

Public test cases

  • Input

    2  1 2
3  2 1  3 2
4  4 3  1 2  2 3
5  3 1  3 4  3 5  4 2

    Output

    NO
NO
SI
SI
    • Information
    Author
    Manuel Torres
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++