Drevesa
Objavljeno: Če Maj 18, 2017 12:18 pm
Pri svojem raziskovalnem delu se Janez ukvarja z dvojiškimi drevesi. Da bi sodelavcu dokazal svojo superiornost, je skonstruiral dvojiško drevo, ki je protiprimer za sodelavčevo domnevo. Žal pa je protiprimer zapisal na list, ki se je izgubil med stotinami podobnih listov na njegovi pisalni mizi (kot pri večini raziskovalcev, urejenost ni ravno Janezova močna točka). Da bi bilo vse skupaj še hujše, si Janez ni zapisal vseh podatkov o drevesu, ampak je za vsako vozlišče zgolj zabeležil, katero je njegovo nadrejeno vozlišče. Spomni pa se, da je bilo skonstruirano drevo levo poravnano.
Ker je vseh dreves na listih na njegovi pisalni mizi občutno preveč, da bi v nekaj dnevih uspel poiskati pravega, te je prosil za pomoč. Zelo bi mu pomagal že s tem, če bi iz množice podatkov o drevesih izbral le takšne, ki bi lahko predstavljali levo poravnano dvojiško drevo.
Poduk: Levo poravnano dvojiško drevo je polno drevo, ki mu morda manjkajo nekateri listi na desni strani v spodnjem nivoju (glej sliko).
Vhodni podatki
Prva vrstica vhodne datoteke vsebuje eno samo število n, tj. število testnih primerov. V prvi vrstici vsakega primera je število vozlišč dvojiškega drevesa m, nato pa sledi za vsako vozlišče po ena vrstica, ki vsebuje dve števili: [math] in [math]. Število [math] predstavlja enolično oznako vozlišča, število [math] pa oznako njegovega starša. Če je vozlišče [math] koren drevesa, je [math] enak −1. Podatki zagotovo predstavljajo neko dvojiško drevo.
Omejitve vhodnih podatkov
Izhodni podatki
Za vsak testni primer izpiši po eno številko (vsako v svoji vrstici):
1, če podatki lahko predstavljajo levo poravnano dvojiško drevo in 0 sicer.
Primer vhoda
Pripadajoč izhod
Ker je vseh dreves na listih na njegovi pisalni mizi občutno preveč, da bi v nekaj dnevih uspel poiskati pravega, te je prosil za pomoč. Zelo bi mu pomagal že s tem, če bi iz množice podatkov o drevesih izbral le takšne, ki bi lahko predstavljali levo poravnano dvojiško drevo.
Poduk: Levo poravnano dvojiško drevo je polno drevo, ki mu morda manjkajo nekateri listi na desni strani v spodnjem nivoju (glej sliko).
Vhodni podatki
Prva vrstica vhodne datoteke vsebuje eno samo število n, tj. število testnih primerov. V prvi vrstici vsakega primera je število vozlišč dvojiškega drevesa m, nato pa sledi za vsako vozlišče po ena vrstica, ki vsebuje dve števili: [math] in [math]. Število [math] predstavlja enolično oznako vozlišča, število [math] pa oznako njegovega starša. Če je vozlišče [math] koren drevesa, je [math] enak −1. Podatki zagotovo predstavljajo neko dvojiško drevo.
Omejitve vhodnih podatkov
- n ≤ 100
- m ≤ 100000
- 0 ≤ [math] ≤ 100000
- −1 ≤ b ≤ 100000
Izhodni podatki
Za vsak testni primer izpiši po eno številko (vsako v svoji vrstici):
1, če podatki lahko predstavljajo levo poravnano dvojiško drevo in 0 sicer.
Primer vhoda
Koda: Izberi vse
3
3
5 3
3 -1
7 3
3
1 -1
3 1
7 3
9
1 -1
2 1
3 1
4 2
5 2
6 3
7 3
8 4
9 7
Pripadajoč izhod
Koda: Izberi vse
1
0
0