Državno natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 3. zadatak

Paola se priprema za Međunarodnu informatičku olimpijadu (IOI) koja će se ove godine održati u Japanu. Osim rješavanja zadataka, pripreme za Olimpijadu uključuju i upoznavanje s domaćinom Japanom i njegovom tradicijom, pa Paola u slobodno vrijeme vježba zen, ikebanu i sumo-hrvanje.

Da bi stabalce ikebane bilo u skladu sa zen principima, ono mora biti oblika potpunog binarnog stabla zadane dubine \(D\). Riječ je o stablu u kojem svaki čvor, osim listova (čvorova najveće dubine), ima točno dvoje djece. Na donjoj je slici primjer potpunog binarnog stabla dubine \(3\):

Paolina ikebana je stablo, ali ne nužno binarno, i ne nužno dubine \(D\). Kako bi ikebanu oblikovala na traženi način, Paola može činiti sljedeće operacije:

1. odrezati neki čvor i cijelo njegovo podstablo,
2. odabrati neki čvor i zaliti ga japanskom vodom, nakon čega će svakom čvoru u njegovom podstablu (uključujući i odabrani čvor) izrasti još jedno dijete.

Na novonastalim čvorovima moguće je činiti iste operacije. Napišite program koji pronalazi najmanji ukupan broj operacija kojima se Paolina ikebana može transformirati u potpuno binarno stablo dubine \(D\).

Ulazni podaci

U prvom retku nalaze se prirodan broj \(N\) \((1 \leq N \leq 1 000 000)\), broj čvorova početnog stabla, i cijeli broj \(D\) \((0 \leq D \leq 20)\), tražena dubina potpunog binarnog stabla.

Čvorovi su označeni brojevima od \(1\) do \(N\), pri čemu je korijen označen brojem \(1\) te ima dubinu \(0\).

U \(k\)-tom od idućih \(N - 1\) redaka nalazi se prirodan broj manji ili jednak \(k\), oznaka roditelja čvora \(k + 1\).

Izlazni podaci

U jedini redak ispišite traženi minimalni broj operacija.

Bodovanje

U test podatcima ukupno vrijednima \(10\%\) bodova vrijedit će \(N = 1\).

U test podatcima ukupno vrijednima \(40\%\) bodova početno stablo bit će lanac.

U test podatcima ukupno vrijednima \(30\%\) bodova vrijedit će \(D \leq 2\) i \(N \leq 7\).

U test podatcima ukupno vrijednima \(40\%\) bodova nema dodatnih ograničenja.

Primjeri test podataka

Ulaz

4 2
1
1
2

Izlaz

5

Objašnjenje

Paola može pretvoriti početno stablo u potpuno binarno dubine \(2\) u \(5\) koraka. U prvom koraku Paola zalijeva korijen stabla te tim potezom nastaju četiri nova čvora. Zatim zalijeva čvor s brojem \(3\) te će na stablu izrasti još dva čvora. Iduće tri operacije Paola koristi kako bi odrezala višak stabla. Redom reže čvorove: dijete korijena stabla i dijete čvora \(4\) koji su nastali u prvom koraku te unuka čvora \(3\) koji je nastao u drugom koraku.

Ulaz

1 2

Izlaz

7

Ulaz

10 3
1
2
3
4
1
6
6
8
8

Izlaz

9