No.778 クリスマスツリー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 45
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
2 ProblemId : 2517 / 出題時の順位表

問題文

クリスマスツリーに$N$個の飾りをつけることにしました。
飾りには$0$番から$N-1$番までの番号がついています。
それぞれの飾りの下にはさらに飾りをいくらでも吊るすことができます。
てっぺんに0番の飾りをつけその後は適当な順番で飾りを下に吊るしました。

ある2つの飾りを選ぶ${}_{N}{\rm C}_{2}$通りのうち、2つの飾りが以下の2つの条件を満たすのはいくつか。

・一方の飾りから上に辿るともう一方の飾りにたどり着ける。
・上にある飾りの番号が下にある飾りの番号より小さい。

入力

$N$
$A_1$ $A_2$ $\dots $ $A_{N-1}$

$N$は正の整数。$2 \le N \le 200000$。
$A_i$は$i$番目の飾りが吊るされた1つ上の飾りをあらわす。$0 \le A_i \le N-1$。

出力

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

サンプル

サンプル1
入力
2
0
出力
1

$2$個の飾りをつけます。
0番の飾りの下に1番の飾りが吊るされています。
0番と1番の飾りを選ぶ時、1番から上に辿ると0番に辿り着け、0番は1番より番号が小さいです。
よって、この1通りです。

サンプル2
入力
3
0 0
出力
2

$3$個の飾りをつけます。
0番の飾りの下に1番と2番の飾りが吊るされています。
「0番と1番」、「0番と2番」を選ぶ時に条件を満たします。
「1番と2番」を選ぶ時、どちらからももう一方へ上に辿れないので条件を満たしません。

サンプル3
入力
3
2 0
出力
2

$3$個の飾りをつけます。
0番の飾りの下に2番、2番の飾りの下に1番が吊るされています。
「0番と1番」、「0番と2番」を選ぶ時に条件を満たします。
「1番と2番」を選ぶ時、2番から1番に上に辿れますが、上の2番のほうが番号が大きいため条件を満たしません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。