Uzb Eng

0026. Qirollik sulolasi
: 2 c
: 64

Ali tarixni yaxshi koradi. Agarda unga biror bir aniq sulolani organish vazifasi qoyilsa, u bunga judayam ishtiyoq bilan kirishadi. Ali qonning tozaligiga judayam etibor beradi. Shuning uchun sulolani oraganayotganida faqatgina ularning erkak kishilarini organadi. Chunki ota avlodning asoschilari hisoblanadi.
Sulolalarni tahlil qilishning eng qadimiy usullaridan biri - sulolaning bir nechta azolarining og'il farzandlarini organish sanaladi. Ali esa bu tahlilga ozgartirish kiritmoqchi? Yani ularni faqatgina og'illarini organmasdan, nabira, evara, chevara va boshqalarini ham organmoqchi. Ammo, sulola bir nechta avlodlarga chozilib ketishi mumkin. Demak, umumiy avlodlar soni judayam katta boladi. By esa Aliga qiyinchilik tugdiradi. Madomiki, hozir XXI asr bolsa, shuning uchun Ali dasturchilarga murojaat etishga qaror qildi.
Sulola insonlar toplamidan iborat bolib, ulardan bittasi sulola asoschisi, qolganlari sulola azolari bolib, U ning otasi V boladi. Bunda U V ning ogli sanaladi yoki U orqali 1 avlodi hisoblanadi. U orqali k+1 avlod V ning U orqali k avlodining ogli hisoblanadi. Sulolaning mavjud bolgan bir nechta V azolarining k avlod orqali nechta avlodi borligi Alini qiziqtiradi.
Misoldagi berilgan savol uchun sulolaning 1 raqamli azosini 2 avlodi boyicha ikkita avlodi bor: 3 va 5.

:
Birinchi satrda Ali tadqiq qilayotgan suloladagi odamlar soni n berilgan (1 < n < 105). Sulola azolari 1 dan n gacha bolgan har xil natural sonlar bilan raqamlangan. Keyin n ta son berilgan. I-chisi sulolaning i-chi azosining otasi hisoblanadi yoki -1 bilan ushbu sulolaning asoschisi beriladi. Shunisi malumki, sulola asoschisi bitta boladi. Qolgan ixtiyoriy azo sulola asoschisining avlodi boladi.
Keyingi satrda Alini qiziqtirgan savollar soni m berilgan (1 < n < 105). Keyin esa m ta satr berilgan. U ikkita v va k sonlaridan iborat. (1 < v < n, 1 < k < 109). Mos ravishda tadqiq qilinayotgan sulola azosi raqami va Alini qiziqtirgan avlodlar soni.

:
Berilgan har bir savol uchun berilgan sulola azosining berilgan son boyicha avlodlar sonini bildiruvchi bitta son chiqaring.

5
-1 1 2 1 4
2
1 2
4 7
10
5 5 6 3 3 -1 9 7 6 5
20
8 1
2 1
3 2
6 2
3 2
1 1
7 2
1 1
8 1
6 1
10 2
7 1
8 1
7 1
5 2
10 1
10 1
10 2
4 1
9 2
2
0




0
0
3
3
3
0
0
0
0
2
0
1
0
1
0
0
0
0
0
1
:
: XII 2011


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.