**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 ?
 

Dandu-vi-se un arbore binar cu $N$ noduri, inradacinat in nodul $1$, trebuie sa calculati cati subarbori exista cu proprietatea de **treap**.

h2. Date de intrare
Fişierul de intrare $treap.in$ va contine pe prima linie numarul $N$. Urmatoarele $N-1$ linii vor contine perechi de cate $2$ numere naturale $x, y$ cu proprietatea ca exista muchie intre nodurile $x$ si $y$ in arbore. Urmatoarea linie va contine $N$ numere, al $i$-lea dintre ele fiind $KEY[~i~]$ (adica cheia nodului respectiv). Urmatoarea linie va contine alte $N$ numere, al $i$-lea dintre ele fiind $PRIO[~i~]$ (adica prioritatea nodului respectiv).