Bantu temanmu belajar dengan menambahkan soal di Kujawab. Klik disini..

Olimpiade Sains Provinsi (OSP) 2017 - Komputer , Nomor 47

47

HUBUNGAN KAKEK-CUCU
Pada soal ini, Anda diminta untuk memroses silsilah dinasti kerajaan KITOKI. Setiap lelaki dinasti ini diberi nomor 1, 2, ... , N. Pendiri dinasti kerajaan diberi nomor 1. Anda diberi dafter hubungan ayah-anak, dimana A[Y]=X menyatakan bahwa Y adalah ayah dari X. Dari hubungan ayah-anak, Anda dapat mendeteksi hubungan kakek-cucu karena jlka z adalah ayah dari Y, dan Y adalah ayah dari X, maka Z adalah kakek dari X. Dari sebuah daftar hubungan ayah-anak, Anda diminta untuk membuat sebuah program yang menghitung banyaknya hubungan kakek-cucu.

Format Input :

Masukan terdiri dari 2 baris. Baris pertama berisi bilangan bulat N. Baris kedua berisi N-1 bilangan bulat A[2], A[3], hingga A[N] sesuai penjelasan pada deskripsi soal.

Format Output :

Sebuah baris yang berisi sebuah bilangan bulat yang menandakan banyaknya hubungan kakek-cucu dari data masukan yang diberikan.

Batasan :
1 \leq N \leq 100.000
1 \leq A[i] \leq N
Dijamin bahwa daftar hubungan ayah-anak membentuk silsilah yang valid

Sample input dan output:

9

1 1 3 3 3 4 6 6

6

 

Penjelasan:

Berikut adalah tree yang dibentuk dari masukan di atas.

Terdapat 6 hubungan kakek-cucu pada tree tersebut yakni (1-4), (1-5), (1-6), (3-7), (3-8), dan (3-9).