Treap

treap

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

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':http://www.infoarena.ro/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.
 
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**.
 
**Un arbore** este un graf neorientat conex si aciclic.
 
**Un arbore inradacinat** este un arbore care are radacina fixata.
 
**Un arbore binar** este un arbore cu proprietatea ca fiecare nod din componenta sa are **cel mult** doi fii.
 
**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 determintati care subarbori au proprietatea de **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
- 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 ?

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).

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[~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**
* **Un subarbore inradacinat intr-un nod care nu are fii, este considerat frunza si reprezinta evident un treap**
* Nu se garanteaza ca prioritatile generate sunt aleatoare, treap-ul avand forme dintre cele mai diverse.

**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**
**#Comisia nu putea lasa sa treaca o noua editie a A.G.M fara sa dea o problema cu treapuri**

h2. Exemplu

1 3
5 5 7
100 9 1

| 1 1 1
|
 
table(example). |_. treap.in |_. treap.out |
| 3
1 2
1 3
5 8 7
100 9 1

| 0 1 1
|

table(example). |_. treap.in |_. treap.out |
|3
1 2
2 3
2 1 3
3 2 1
| 0 1 1
|

h3. Explicaţie
 
...

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