F - Subtree Reversi Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

頂点に 1 から N までの番号がついており、頂点 1 を根とする N 頂点の根付き木が与えられます。 この木の頂点 i の親は頂点 p_i です（2\leq i\leq N）。

Alice と Bob は、この木を使って、次のようなゲームを行います。

  • Alice が先手、Bob が後手で、表裏を白と黒に塗り分けた石を使い、交互に 1 つずつ木の頂点に石を置いていく。この際、Alice は白い面を上に、Bob は黒い面を上にして置く。
  • 各手番で石を置いてよいのは、その頂点自身には石が置かれておらず、子孫である頂点には全て石が置かれている頂点のみである。
  • 石を置くとき、置いた頂点の子孫にある石を全て裏返す（置いた石自体は裏返さない）。

全ての頂点に石が置かれるとゲーム終了となり、この時点で白い面が上になっている石の数を Alice の得点とします。

Alice はできるだけ大きな得点を得ようとし、Bob は Alice の得点をできるだけ小さくしようとします。両者が最善の手順を取ったとき、Alice の得点はいくらでしょうか。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq p_i < i (2\leq i \leq N)
  • 入力される値はすべて整数である
  • 与えられるグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

N
p_2 p_3 \ldots p_N

出力

答えを整数で出力せよ。

入力例 1

4
1 1 2

出力例 1

2

与えられた木では、初めに石を置くことのできる頂点は 3,4 のみです。ここから、例えば次のような進行が考えられます。

  • Alice が頂点 4 に白い面を上にして石を置く。この操作の後、頂点 2 は子孫に全て石が置かれたので、石が置けるようになる。
  • Bob が頂点 2 に黒い面を上にして石を置き、頂点 4 にある石を裏返して黒い面を上にする。
  • Alice が頂点 3 に白い面を上にして石を置く。
  • Bob が頂点 1 に黒い面を上にして石を置き、頂点 2,3,4 にある石を全て裏返す。

この場合、ゲーム終了時に頂点 1,2,3,4 にある石はそれぞれ黒、白、黒、白が上になっています。実は、この進行は双方の最善手の一例であり、答えは 2 となります。

入力例 2

7
1 1 2 4 4 4

出力例 2

5

Score : 900 points

Problem Statement

You are given a rooted tree with N vertices numbered from 1 to N, rooted at vertex 1. The parent of vertex i is vertex p_i (2\leq i\leq N).

Alice and Bob play a game using this tree as follows.

  • Alice goes first, and Bob goes second. They take turns placing a stone, with a white side and a black side, on a vertex of the tree. Alice places the stone with the white side up, and Bob places the stone with the black side up.
  • In each turn, a stone can only be placed on a vertex that does not have a stone on itself while all its descendants already have stones on them.
  • When placing a stone on a vertex, all the stones on the descendants of that vertex are flipped over (the placed stone itself is not flipped).

The game ends when all vertices have stones. Alice's score is the number of stones with the white side up at this point.

Alice tries to maximize her score, and Bob tries to minimize Alice's score. If both play optimally, what will be Alice's score?

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq p_i < i (2\leq i \leq N)
  • All input values are integers.
  • The given graph is a tree.

Input

The input is given from Standard Input in the following format:

N
p_2 p_3 \ldots p_N

Output

Print the answer as an integer.

Sample Input 1

4
1 1 2

Sample Output 1

2

In the given tree, the only vertices where a stone can be placed initially are 3 and 4. One possible progression from here is as follows.

  • Alice places a stone with the white side up on vertex 4. After this operation, all descendants of vertex 2 have stones, so it is now possible to place a stone on vertex 2.
  • Bob places a stone with the black side up on vertex 2 and flips the stone on vertex 4 to have the black side up.
  • Alice places a stone with the white side up on vertex 3.
  • Bob places a stone with the black side up on vertex 1 and flips all the stones on vertices 2, 3, and 4.

In this case, at the end of the game, the stones on vertices 1, 2, 3, and 4 have black, white, black, and white sides up, respectively. In fact, this progression is an example of optimal sequences of moves for both players; the answer is 2.

Sample Input 2

7
1 1 2 4 4 4

Sample Output 2

5