No.778 Christmas Tree
タグ : / 解いたユーザー数 140
作問者 :
nmnmnmnmnmnmnm
Problem Statement
We have decided to put $N$ ornaments on a Christmas tree.
The ornaments are numbered from $0$ to $N-1$.
Any number of further ornaments can be hung below each ornament.
Ornament 0 was placed at the very top, and after that the ornaments were hung below in some arbitrary order.
Among the ${}_{N}{\rm C}_{2}$ ways to choose two ornaments, how many satisfy both of the following two conditions?
・Going upward from one of the ornaments, you can reach the other ornament.
・The number of the upper ornament is smaller than the number of the lower ornament.
Input
$N$
$A_1$ $A_2$ $\dots $ $A_{N-1}$
$N$ is a positive integer. $2 \le N \le 200000$.
$A_i$ denotes the ornament one level above, from which ornament $i$ is hung. $0 \le A_i \le N-1$.
Output
Output the answer on one line.
Print a newline at the end.
Sample
Sample 1
Input
2 0
Output
1
We put on $2$ ornaments.
Ornament 1 is hung below ornament 0.
When choosing ornaments 0 and 1, going upward from ornament 1 reaches ornament 0, and ornament 0 has a smaller number than ornament 1.
Therefore, there is this 1 way.
Sample 2
Input
3 0 0
Output
2
We put on $3$ ornaments.
Ornaments 1 and 2 are hung below ornament 0.
The conditions are satisfied when choosing "0 and 1" or "0 and 2".
When choosing "1 and 2", neither can be reached from the other by going upward, so the conditions are not satisfied.
Sample 3
Input
3 2 0
Output
2
We put on $3$ ornaments.
Ornament 2 is hung below ornament 0, and ornament 1 is hung below ornament 2.
The conditions are satisfied when choosing "0 and 1" or "0 and 2".
When choosing "1 and 2", you can go upward from ornament 1 to ornament 2, but the upper ornament 2 has the larger number, so the conditions are not satisfied.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。