TR-H1. Ikki qishloq orasi

n ta qishloq n − 1 ta yo‘l bilan daraxt shaklida ulangan, j-yo‘l uzunligi wⱼ. Pochta xizmati q ta so‘rovga javob berishi kerak: u qishloqdan v qishloqqacha (yagona yo‘l bo‘ylab) masofa qancha?

Kirish ma’lumotlari

Birinchi qatorda n, keyin n − 1 qatorda a b w. Keyin q, so‘ng q qatorda u v.

Chiqish ma’lumotlari

Har so‘rovga alohida qatorda masofa.

Cheklovlar

1 ≤ n, q ≤ 2·10⁵; 1 ≤ w ≤ 10⁹. Javob 64 bitli.

1-misol: 4 dan 5 gacha 4 → 2 → 1 → 3 → 5: 3 + 1 + 6 + 2 = 12.