Qarışqa koloniyası
Qrup qarışqalar böyük və möhtəşəm bir koloniya qurduqları üçün fəxr edirlər. Lakin koloniyanın böyük ölçüsü bəzi problemlər yaradıb, çünki bir çox qarışqa koloniyanın bəzi hissələri arasında yolu tapa bilmir. Onlar sizin köməyinizə ehtiyac duyurlar!
Qarışqa koloniyası n qarışqa yuvasından ibarət bir sıra kimi tunellərlə birləşdirilib. Qarışqalar, qabaqcadan düşünərək, tikinti prosesində qarışqa yuvalarını ardıcıl olaraq nömrələyiblər. Birinci qarışqa yuvası, 0 nömrəli, heç bir tunelə ehtiyac duymurdu, lakin hər bir sonrakı qarışqa yuvası, 1-dən n − 1-ə qədər, yeni qarışqa yuvasını mövcud qarışqa yuvalarından biri ilə birləşdirən bir tunel tikdilər. Bu tunel kifayət idi ki, hər hansı bir qarışqa əvvəl tikilmiş hər hansı bir qarışqa yuvasına gedə bilsin, bəlkə də yolunda digər qarışqa yuvalarından keçərək. Buna görə də onlar əlavə tunellər yaratmaq barədə narahat olmadılar və daha çox qarışqa yuvası tikməyə davam etdilər.
Sizin vəzifəniz koloniyanın strukturunu və sorğular dəstini nəzərə alaraq, hər bir sorğu üçün qarışqa yuvaları cütləri arasında ən qısa yolu hesablamaqdır. Yolun uzunluğu keçilməsi lazım olan bütün tunellərin uzunluqlarının cəmidir.
Giriş məlumatları
Hər bir test bir neçə sətirdən ibarətdir. Birinci sətir koloniyada qarışqa yuvalarının sayı n (2 ≤ n ≤ 10^5) ehtiva edir. Növbəti n − 1 sətirin hər biri tuneli təsvir edən iki rəqəm ehtiva edir. i-ci sətir (1 ≤ i ≤ n − 1) A[i] və L[i] ehtiva edir, bu da i nömrəli qarışqa yuvasının A[i] qarışqa yuvası ilə L[i] uzunluğunda tunellə birbaşa birləşdiyini göstərir (0 ≤ A[i] ≤ i − 1 və 1 ≤ L[i] ≤ 10^9). Növbəti sətir sorğuların sayını q (1 ≤ q ≤ 10^5) ehtiva edir. Növbəti q sətirin hər biri sorğunu təsvir edir və iki fərqli rəqəm s və t (0 ≤ s, t ≤ n − 1) ehtiva edir - arasında məsafəni tapmaq lazım olan qarışqa yuvalarının nömrələri.
Son testdən sonra bir sıfırdan ibarət sətir gəlir.
Çıxış məlumatları
Hər bir test üçün q tam ədəd olan bir sətir çıxarın, hər biri sorğu qarışqa yuvaları cütləri arasında ən qısa yolun uzunluğudur. Nəticələri giriş məlumatlarında sorğuların verildiyi ardıcıllıqla yazın.