Delete and Delete 2

2 secs 1024 MB
first_vil's icon first_vil

問題文

NN 頂点からなり、頂点 11 を根とする根付き木があります。頂点 i (2iN)i\ (2 \le i \le N) の親は頂点 PiP_i です。 これからあなたは以下の操作を繰り返します。

  • 根以外の頂点が存在するなら、それらのうち一つを選び、以下に示す「吸収」を行う。その後、葉となっている根以外の頂点を全て削除する。
    • 頂点 xx に対する吸収:頂点 xx が葉でなければ、「頂点 xx の子」の子は全て頂点 xx の子に変更され、元々の頂点 xx の子は全て削除される。頂点 xx が葉であれば、頂点 xx が削除される。

根以外の頂点を全て削除するまでに行う操作の回数の最小値を求めてください。

制約

  • 入力はすべて整数
  • 2N1052 \le N \le 10^5
  • 1Pi<i (2iN)1 \le P_i \lt i\ (2 \le i \le N)

入力

NN
P2P_2 P3P_3 \dots PNP_N

出力

答えを出力し、最後に改行してください。

サンプル1

入力
4
1 2 1
出力
1

サンプル2

入力
7
1 2 3 2 4 2
出力
2

サンプル3

入力
15
1 1 1 3 1 5 4 3 1 4 9 4 5 4
出力
2

Submit


Go (1.21)