Задача №115238. Кооперативная игра на дереве
Сережа и Азат любят играть в настольные игры. После многих часов, проведенных в ожесточенных схватках друг с другом, ребята утомились и решили попробовать сыграть в кооперативные игры — в них игроки должны сотрудничать друг с другом, вместе добиваясь наилучшего результата. К счастью ребят, как раз недавно Азату подарили одну такую игру.
В этой игре имеется корневое дерево из \(n\) вершин с корнем в вершине \(1\), а также набор фишек — одна синяя и много красных. Изначально в вершину \(1\) помещается одна синяя и одна красная фишка. Далее совершаются следующие шаги:
- Первый игрок передвигает синюю фишку из той вершины, где она находится, в одного из сыновей.
- Если синяя фишка оказалась в листе (то есть в вершине, у которой нет сыновей), то игра заканчивается.
- Второй игрок поступает аналогично с красной фишкой: он передвигает ее из вершины, где она находится, в одного из ее сыновей.
- Если красная фишка оказалась в листе, то она навсегда остается там, и ее больше нельзя перемещать, но зато новая красная фишка помещается в вершину, где сейчас находится синяя. После этого игра продолжается с шага \(1\).
Цель игры состоит в том, чтобы в конце на дереве оказалось как можно больше красных фишек. Однако разработчики игры не указали, какого наилучшего результата в ней можно достичь, поэтому ребята просят вас определить его.
В первой строке дано число \(n\) (\(2 \le n \le 2\cdot 10^5\)) — количество вершин в дереве. В следующей строке заданы \(n-1\) чисел \(p_2, p_3, \ldots p_n\), где число \(p_i\) означает, что вершина \(i\) является сыном вершины \(p_i\) (\(1 \le p_i < i\)).
Выведите одно число — максимальное количество красных фишек, которые могут оказаться на дереве в конце игры.
В первом примере оптимальная последовательность действия такая: первый игрок передвигает свою фишку в вершину \(3\), а второй — в вершину \(2\). После этого новая красная фишка появляется в вершине \(3\), первый игрок двигает синюю фишку в вершину \(4\), и на этом игра заканчивается.
4 1 1 3
2
3 1 2
1