== include(page="template/taskheader" task_id="treap") ==

- Arbore (graf neorientat conex si **aciclic**) cu N noduri
- Arbore binar (fiecare nod are cel putin 0 fii si cel mult doi fii)
- Arbore inradacinat in nodul 1

Undeva intr-un univers paralel, Piromanul a ajuns sa iubeasca apa si nu focul ca de obicei. Totusi, nu s-a schimbat prea mult...inca ii plac treapurile, ca in problema Metro. Gandindu-se ca comisia A.G.M s-ar face de ras daca ar lasa sa treaca cea de-a treia editie fara o problema cu treapuri, s-a gandit sa aibe grija de imaginea tuturor colegilor sai.

-Cati subarbori exista cu proprietatea ca orice nod am alege din acel subarbore, nodul respectiv are prioritatea mai mare sau egala cu a fiilor sai si cheia acelui nod este mai mare sau egala cu a unuia dintre fii daca acel fiu exista si mai mica strict decat a celuilalt fiu daca acesta exista ?-

Piro, baiat fin de altfel, nu isi doreste sa fie chiar cel mai antipatizat membru al comisiei, asa ca va face o scurta incursiune impreuna cu voi in ceea ce inseamna **tainele treap-ului**.

De la Ceterchi citire:

**Un arbore** este un graf neorientat conex si aciclic.

Un arbore binar de căutare este un arbore binar cu următoarele proprietăţi:

**Un arbore inradacinat** este un arbore care are radacina fixata.

* fiecare nod are o valoare asociată;
* pentru fiecare nod, subarborele stâng conţine valori mai mici sau egale decât cea a nodului, iar cel drept conţine valori mai mari sau egale decât cea a nodului

**Un arbore binar** este un arbore cu proprietatea ca fiecare nod din componenta sa are **cel mult** doi fii.

* fiecare nod are prioritatea mai mare sau egala cu cea a fiilor sai (+ treap)

**Un arbore binar de cautare** este un arbore binar cu urmatoarele proprietati:
      -fiecare nod are o valoare asociata
      -pentru fiecare nod, subarborele stang contine valori mai mici sau egale decat cea a nodului, iar cel drept contine valori mai mari                strict decat cea a nodului
**Un max-heap** este un arbore binar cu proprietatea ca fiecare nod are o valoare asociata si, in plus, valoarea asociata unui nod este mai mare sau egala cu cea asociata fiilor sai.
 
**Un treap** este un arbore cu proprietatea ca fiecare nod are asociat doua valori : cheie si prioritate. Daca ne uitam doar la cheile nodurilor, facand abstractie de prioritati, atunci acesta este **arbore binar de cautare**. Daca ne uitam la prioritatile nodurilor, facand abstractie de chei, atunci acesta este **max-heap**.
 
Dandu-vi-se un arbore binar cu n noduri, inradacinat in nodul 1, trebuie sa calculati cati subarbori exista cu proprietatea ca pentru orice nod am alege din acel subarbore, nodul respectiv are prioritatea mai mare sau egala cu a fiilor sai si cheia acelui nod este mai mare sau egala cu a unuia dintre fii daca acel fiu exista si mai mica strict decat a celuilalt fiu daca acesta exista ?

h2. Date de intrare