És un AVL? P34834


Statement
 

pdf   zip

thehtml

Considereu un arbre representat amb un graf dirigit amb n vèrtexs i n−1 arcs, on cada arc xy indica que el node amb clau x és pare del node amb clau y. Digueu si l’arbre representat pot ser un arbre binari de cerca AVL o no. Podeu triar l’ordre més convenient per als fills de cada clau.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida d’n claus diferents, seguides de n−1 parells x y, indicant que x és pare de y. Suposeu 1 ≤ n ≤ 104, que les claus són enters entre −109 i 109, i que el graf representa un arbre.

Sortida

Per a cada graf, escriviu “yes” si representa un arbre binari de cerca AVL, i “no” altrament.

Public test cases
  • Input

    1  42
    
    2  1000000000 -1000000000
    -1000000000 1000000000
    
    3  0 2 4
    0 2  0 4
    
    3  0 2 4
    2 4  2 0
    
    3  0 2 4
    0 2  2 4
    
    4  1 3 5 7
    3 1  3 7  3 5
    
    4  1 3 5 7
    5 1  5 7  7 3
    
    8  0 -2 2 -4 4 -6 6 -8
    4 0  -8 -6  -4 -8  0 2  0 -2  -4 4  4 6
    
    8  0 -2 -1 -4 4 -6 6 -8
    4 0  -8 -6  -4 -8  0 -1  0 -2  -4 4  4 6
    

    Output

    yes
    yes
    no
    yes
    no
    no
    no
    yes
    no
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++