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

- Arbore (graf neorientat conex si aciclic) cu N noduri

- 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

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

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

De la Ceterchi citire:

* 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

* fiecare nod are prioritatea mai mare sau egala cu cea a fiilor sai (+ 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]. Urmatoarea linie va contine alte N numere, al i-lea dintre ele fiind PRIO [i].

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~]$. Urmatoarea linie va contine alte $N$ numere, al $i$-lea dintre ele fiind $PRIO[~i~]$.

h2. Date de ieşire

În fişierul de ieşire $treap.out$ se va afisa un sir de N numere dupa cum urmeaza : al i-lea numar din sir va fi 1 daca subarborele inradacinat in nodul i are proprietatea de treap si 0 altfel. **Numerele vor fi afisate cu spatii intre ele**

În fişierul de ieşire $treap.out$ se va afisa un sir de $N$ numere dupa cum urmeaza : al $i$-lea numar din sir va fi $1$ daca subarborele inradacinat in nodul $i$ are proprietatea de treap si $0$ altfel. **Numerele vor fi afisate cu spatii intre ele**.

h2. Restricţii

**1 <= N <= 150.000**
**1 <= KEY <= 1.000.000.000**
**1 <= PRIO <= 1.000.000.000**
**Arborele se considera ca este inradacinat in nodul 1**
**La finalul fisierului de iesire este '\n', nu spatiu**

**$1 <= N <= 150,000$**
**$1 <= KEY[~i~] <= 10^9^$**
**$1 <= PRIO[~i~] <= 10^9^$**
**Arborele se considera ca este inradacinat in nodul $1$**
**La finalul fisierului de iesire este $'\n'$, nu spatiu**

**#Comisia nu putea lasa sa treaca o noua editie a A.G.M fara sa dea o problema cu treapuri**
**Un subarbore inradacinat intr-un nod care nu are fii, este considerat frunza**