Problem description

Back
Show PDF
Gra w Grę I
(Y)
Limit pamięci: 1024 MB
Limit czasu: 2.00 s

Krasnale Algoś i Buguś postanowili rozegrać pojedynek w Krasnalowe Reversi. Zamiast zwykłej planszy wybrali ukorzenione drzewo.

Dane jest ukorzenione drzewo o N wierzchołkach ponumerowanych od 1 do N. Korzeniem drzewa jest wierzchołek 1. Dla każdego wierzchołka i takiego, że 2 ≤ i ≤ N, jego ojcem jest wierzchołek Pi.

Na początku na żadnym wierzchołku nie leży żeton. Każdy żeton ma dwie strony: białą i czarną.

Krasnale wykonują ruchy na przemian. Pierwszy ruch należy do Algosia. W swoim ruchu Algoś kładzie żeton białą stroną do góry, a Buguś — czarną.

W jednym ruchu można położyć żeton na wierzchołku u tylko wtedy, gdy spełnione są oba poniższe warunki:

  • na wierzchołku u nie leży jeszcze żaden żeton,
  • na wszystkich potomkach wierzchołka u leżą już żetony.

Potomkami wierzchołka u są wszystkie wierzchołki znajdujące się niżej w jego poddrzewie. Wierzchołek u nie jest swoim własnym potomkiem.

Po położeniu żetonu na wierzchołku u wszystkie żetony leżące na jego potomkach zostają odwrócone na drugą stronę: z białej na czarną albo z czarnej na białą. Żeton właśnie położony na wierzchołku u nie zostaje odwrócony.

Gra kończy się, gdy na każdym wierzchołku leży żeton. Wynikiem Algosia jest liczba żetonów, które po zakończeniu gry leżą białą stroną do góry.

Algoś chce zmaksymalizować swój wynik, a Buguś chce go zminimalizować. Wyznacz wynik Algosia przy optymalnej grze obu krasnali.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę wierzchołków drzewa.

W drugim wierszu znajduje się N − 1 liczb naturalnych P2, P3, …, PN. Liczba Pi oznacza numer ojca wierzchołka i.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą: wynik Algosia przy optymalnej grze obu krasnali.

Ograniczenia

2 ≤ N ≤ 200 000, 1 ≤ Pi < i dla każdego 2 ≤ i ≤ N.

Przykłady

Wejście Wyjście Wyjaśnienie 
4
1 1 2

2

Na początku gry żeton można położyć tylko na wierzchołkach 3 oraz 4. Jedna z możliwych rozgrywek wygląda następująco:

  • Algoś kładzie żeton białą stroną do góry na wierzchołku 4.
  • Buguś kładzie żeton czarną stroną do góry na wierzchołku 2 i odwraca żeton na wierzchołku 4 na czarną stronę.
  • Algoś kładzie żeton białą stroną do góry na wierzchołku 3.
  • Buguś kładzie żeton czarną stroną do góry na wierzchołku 1 i odwraca żetony na wierzchołkach 2, 3 oraz 4.

Na koniec tej rozgrywki żetony na wierzchołkach 1, 2, 3, 4 leżą odpowiednio czarną, białą, czarną i białą stroną do góry. Jest to jedna z optymalnych rozgrywek dla obu krasnali, więc odpowiedź wynosi 2. Jest to najlepszy wynik, jaki może uzyskać Algoś przy optymalnej grze Bugusia.
Wejście Wyjście 
7
1 1 2 4 4 4

5