No.778 クリスマスツリー
nmnmnmnmnmnmnm問題文
クリスマスツリーに$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番のほうが番号が大きいため条件を満たしません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。