Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Drugi dan natjecanja - 3. zadatak

Binarno stablo je hijerarhijska struktura koja se sastoji od n čvorova označenih redom brojevima od 1 do n.

Svaki čvor stabla k može imati lijevo dijete lk te desno dijete rk.

Ako je čvor m dijete čvora k onda kažemo da je k roditelj čvora m, te također kažemo da su k i m susjedni čvorovi.

Čvor označen brojem 1 nazivamo korijen binarnog stabla te uvijek vrijedi da korijen nema roditelja, dok svaki drugi čvor ima jedinstvenog roditelja.

Potomci nekog čvora k su svi čvorovi od kojih se može doći do k prateći niz roditelja te vrijedi da su svi čvorovi (osim samog korijena) potomci korijena stabla.

U svakom čvoru je zapisana vrijednost – prirodni broj između 1 i n uključivo.

Za binarno stablo kažemo da je binarno stablo traženja ako za svaki čvor k stabla vrijedi:

• Ako k ima lijevo dijete lk, onda je vrijednost čvora lk te svih njegovih potomaka manja ili jednaka od vrijednosti čvora k.

• Ako k ima desno dijete rk, onda je vrijednost čvora rk te svih njegovih potomaka veća ili jednaka od vrijednosti čvora k.

  

Zadano je binarno stablo koje je potrebno pretvoriti u binarno stablo traženja kroz niz koraka, gdje u svakom koraku možemo odabrati vrijednost zapisanu u nekom čvoru stabla k te je obrisati iz čvora k i zapisati u neki čvor susjedan čvoru k.

Dozvoljeno je da u međukoracima prilikom pretvorbe u čvoru piše više od jedne vrijednosti ili da ne piše niti jedna, ali u konačnom binarnom stablu traženja opet mora u svakom čvoru pisati točno jedna vrijednost.

Pronađite minimalan broj koraka potreban da se zadano binarno stablo pretvori u binarno stablo traženja.

Ulazni podaci

Prvi red ulaza sadrži prirodni broj n (n ≤ 300 000) – broj čvorova stabla.

Slijedi n redova, k-ti od sljedećih n redova sadrži dva cijela broja lk i rk (0 ≤ lk, rk ≤ n) – oznake lijevog odnosno desnog djeteta čvora k. Ukoliko čvor nema lijevo odnosno desno dijete, lk odnosno rk će biti nula.

U sljedećem redu nalazi se n prirodnih brojeva v1, . . . , vn (1 ≤ vk ≤ n) – početne vrijednosti zapisane u čvorovima redom od 1 do n.

Izlazni podaci

Ispišite traženi minimalni broj koraka.

Primjer zadatka

Ulaz

3
2 3
0 0
0 0
1 2 2

Izalz

2

Ulaz

5
5 4
0 0
0 0
0 3
0 2
2 5 3 2 5

Izlaz

12

Ulaz

8
5 2
0 0
0 0
0 0
6 7
3 0
4 8
0 0
3 1 3 1 2 2 1 4

Izlaz

20