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 N 100.000
1 A[i] 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).