Ağac Ayrılması#3569
Ağac, kompüter elmlərində ən çox istifadə olunan verilənlər strukturlarından biridir. Ağaclar özləri çox çevikdir, lakin mövcud kompüter arxitekturası ilə tam uyğun gəlmirlər. Mövcud arxitektura yaddaşı bir ölçülü massiv kimi qəbul edir. Ağac isə bir ölçülü struktur olmadığından, ağacı yaddaşda yerləşdirərkən keş səmərəliliyi məsələsi ortaya çıxa bilər. Məlumat keşdə saxlanıldıqda, ona daha sürətli daxil olmaq mümkündür. Keş performansını artırmaq üçün ağacın düyünlərinin yerləşdirilməsini nəzərdən keçirək.
Ağacın yerləşdirilmə xərci aşağıdakı kimi müəyyən edilir. Sadəlik üçün yaddaşı hər biri maksimum B ağac düyününü saxlaya bilən bloklara bölünmüş kimi qəbul edirik. Blokdakı məlumatlara daxil olduqda, blokdakı bütün məlumatlar keşdə saxlanılır və beləliklə, blokdakı məlumatlara daxil olma daha sürətli olur. Əgər düyün u-ya v-dən sonra daxil olunursa və hər ikisi eyni blokdadırsa, xərci 0-dır, əks halda 1-dir. Əvvəlcə, keşdə heç bir məlumat yoxdur və hər bir düyünə daxil olmanın xərci həmişə 1-dir. v_1, v_2, ..., v_n yolunun xərci, bu sırayla v_1, v_2, ..., v_n düyünlərinə daxil olduğumuz zaman xərclərin cəmidir. Ağac üçün yerləşdirmə xərci, kök düyündən hər bir terminal düyünə qədər olan yolların maksimum xərci kimi müəyyən edilir.
Aşağıdakı şəkillər, B = 4 və düyün 1 kök düyün olduğu zaman yerləşdirmə nümunələrini göstərir (bu, üçüncü nümunə girişində təsvir edilən ağaca uyğundur). Hər bir çərçivə bir bloku təmsil edir. Sol şəkil, xərci 3 olan yerləşdirmə nümunəsidir. Bu optimal deyil, çünki sağdakı nümunə optimal yerləşdirmə xərci 2-yə nail olur.
Verilmiş ağac üçün, ağacdakı hər bir i düyünü üçün, i düyünü kök düyün olduqda yerləşdirmənin minimum xərcini hesablayın.
Giriş bir neçə test halını ehtiva edir. Hər bir test halı bir sətirdə iki tam ədəd N (1 ≤ N ≤ 100000) və B (1 ≤ B ≤ N) ilə başlayır, bir boşluqla ayrılmışdır. Növbəti N−1 sətirin hər biri bir tam ədəd ehtiva edir. i-ci tam ədəd p_i (1 ≤ p_i ≤ i) göstərir ki, i+1 düyünü və p_i düyünü bağlıdır. Düyünlər 1-dən N-ə qədər nömrələnir.
Son test halı iki sıfırdan ibarət bir sətirlə tamamlanır.
Hər bir test halı üçün, onun hal nömrəsini çap edin. Sonra N sətir çap edin. i-ci sətir, verilmiş ağacın i düyünü kök düyün olduqda yerləşdirmənin minimum xərcini göstərən bir tam ədəd ehtiva etməlidir.
Nümunə çıxış formatına uyğun olun.
Nümunə 1