Lýsing

Fyrirtæki samanstendur af $n$ meðlimum með starfsmannanúmer $1, 2, \dots, n$. Meðlimur $1$ er yfirmaðurinn og sérhver annar meðlimur $i$ ($2 \le i \le n$) á sér beinan yfirmann $f_i$ ($1 \le f_i < i$). Skipurit fyrirtækisins myndar rótarsett tré þar sem meðlimur $1$ er í rótinni.

Í þessu fyrirtæki þekkir meðlimur $a$ meðlim $b$ ef og aðeins ef að minnsta kosti eitt af eftirfarandi skilyrðum er uppfyllt:

• $a = b$.
• $b$ er forfaðir $a$. Með öðrum orðum, til er runa $u_1, u_2, \dots, u_k$ ($2 \le k$) þannig að $u_1 = a$, $u_k = b$ og $u_i = f_{u_{i-1}}$ fyrir öll $2 \le i \le k$.
• $b$ er beint barn $a$ ($b$ er beinn undirmaður $a$). Með öðrum orðum, $f_b = a$.

Athugið að kunningjasambandið er ekki endilega samhverft; þótt $a$ þekki $b$ þýðir það ekki að $b$ þekki $a$.

Nú eru meðlimirnir að spila leik. Í hverri umferð er tiltekinn meðlimur $m$ ágiskarinn, og annar meðlimur $p$ er skotmarkið. Tryggt er að $p$ sé meðlimur sem $m$ þekkir ekki.

Til að bera kennsl á $p$ spyr $m$ runu spurninga. Í hverri spurningu velur $m$ starfsmannanúmer $x$ og spyr: „Þekkir $p$ meðlim $x$?“ Meðlimur $p$ svarar alltaf satt. Að auki, ef $x = p$, mun $p$ sérstaklega ljóstra því upp að hann sé meðlimur $x$, og þá lýkur leiknum.

Hver spurning hefur í för með sér ferðakostnað sem byggist á tré fyrirtækisins. Ef $i$-ta spurningin varðar meðlim $x_i$, þá er kostnaður þeirrar spurningar $dis(x_{i-1}, x_i)$, þar sem $dis(a, b)$ er fjöldi leggja á ótvíræða veginum milli $a$ og $b$ í trénu. Fyrir fyrstu spurninguna ($i = 1$) er kostnaðurinn $dis(m, x_1)$.

Meðlimur $m$ er afar klár og notar bestu mögulegu herkænsku til að lágmarka heildarkostnaðinn sem þarf til að tryggja að leiknum ljúki í versta tilfelli (worst-case scenario). Verkefni þitt er að reikna þennan lágmarkskostnað í versta tilfelli fyrir hvern mögulegan ágiskara $m \in \{1, 2, \dots, n\}$.

Ef meðlimur $m$ þekkir nú þegar alla í fyrirtækinu er svarið fyrir það $m$ jafnt $0$.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $n$ ($1 \le n \le 10^5$), sem táknar heildarfjölda meðlima í fyrirtækinu.

Önnur línan inniheldur $n - 1$ heiltölur sem tákna $f_2, f_3, \dots, f_n$. Það gildir að $1 \le f_i < i$.

Úttak

Prentaðu eina línu sem inniheldur $n$ heiltölur sem tákna svörin fyrir tilvikin þar sem $m = 1, m = 2, \dots, m = n$. Heiltölurnar eiga að vera aðskildar með bilum.

Dæmi

Sýnidæmi inntak 1

3
1 1

Sýnidæmi úttak 1

0 2 2

Sýnidæmi inntak 2

5
1 1 3 2

Sýnidæmi úttak 2

4 3 3 4 4

Sýnidæmi inntak 3

6
1 1 2 2 3

Sýnidæmi úttak 3

4 3 5 4 4 6

Athugasemd

Til að útskýra tilvikið $m = 4$ í sýnidæmi 3: Í fyrsta lagi, eins og sýnt er á myndinni, þekkir meðlimur $m$ ekki meðlimina $\{3, 5, 6\}$. Ein möguleg besta herkænska er að spyrja fyrst hvort $p$ þekki meðlim $2$, sem kostar $1$. Ef svo er gefur það til kynna að $p = 5$, og næsta skref er að spyrja um meðlim $5$ til að ljúka leiknum með heildarkostnaði $2$. Annars er haldið áfram og spurt hvort $p$ þekki meðlim $3$, sem kostar $2$. Ef $p = 3$ lýkur leiknum með heildarkostnaði $3$. Annars gefur það til kynna að $p = 6$, og næsta skref kostar $1$ til að spyrja um meðlim $6$, sem lýkur leiknum með heildarkostnaði $4$. Því krefst þessi herkænska kostnaðar upp á $4$ í versta tilfelli. Hægt er að sanna að engin önnur herkænska getur minnkað fyrirspurnarkostnaðinn í versta tilfelli enn frekar.