Problem B
Klifra upp stigann

Mynd frá pngimg, pngimg.com

Þú ert kominn með kort af tölvukerfi tölvuþrjótanna sem þú ert að reyna stoppa. Hver þrjótur er með yfirmann sem hann ræðir öll sín plön við, fyrir utan einn leiðtoga sem er yfirmaður sjálfs síns. Þú vilt komast inn í tölvu leiðtogans. Þegar þú reynir að komast inn í tölvu, þá geta undirmenn tölvuþrjótsins sem á þá tölvu tekið eftir slíkum aðgerðum, því þeir fá engin eða grunsamleg svör við spurningum sínum um plön sín. Því til að taka yfir tölvu einstaklings þarf fyrst að ná stjórn á tölvu allra undirmanna. Þetta telur aðeins tölvur hjá þeim sem eru með þennan einstakling sem yfirmann, ekki yfirmann yfirmanns þeirra og svo framvegis.

Til þess að sem lægstar líkur eru á að einhver taki eftir aðgerðum þínum viltu stjórna sem fæstum tölvum í einu. Þú getur alltaf skorið á tengingu við tölvu og látið frá stjórn á henni.

Gefið hver er yfirmaður hvers, hvað þarftu að stjórna mörgum tölvum í einu í minnsta lagi til að ná stjórn á tölvu leiðtogans án þess að neinn verði var við?

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$, fjöldi tölvuþrjóta með $1 \leq n \leq 200\, 000$.

Næst koma $n - 1$ línur þar sem $i$-ta línan inniheldur eina heiltölu $p_{i+1}$ sem lýsir hver er yfirmaður tölvuþrjóts $i+1$, þar sem $1 \leq p_{i+1} < i + 1$. Tölvuþrjótur $1$ er sá eini sem hefur engann yfirmann, þar sem hann er forstjóri tölvuþrjótanna.

Úttak

Skrifaðu út eina heiltölu sem táknar minnsta fjölda tölva sem þarf að hafa stjórn á samtímis til að ná stjórn á tölvu leiðtogans.

Útskýring á sýnidæmum

Í fyrsta sýnidæminu byrjum við á að ná stjórn á tölvum $5, 6, 2$ í þeirri röð. Þá erum við með $3$ tölvur samtímis. Sleppum svo $5, 6$ og náum næst $4, 3$ í þeirri röð. Getum þá sleppt $4$ og loks náð $1$. Þá klárum við með mest $3$ tölvur í einu, og ekki er hægt að gera betur.

Figure 1: Sýnidæmi 1

Figure 2: Sýnidæmi 2

6
1
1
3
2
2

3

14
1
2
1
4
5
4
7
8
7
1
11
12
11

4