É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 x → y 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++