TR-H2. Yo‘l bo‘yidagi bekatlar

n ta bekat n − 1 ta yo‘l bilan daraxt shaklida ulangan. i-bekatda aᵢ kg yuk bor. q ta amal:

• 1 v x — v bekatdagi yuk x kg ga teng bo‘ldi;
• 2 u v — u dan v gacha yagona yo‘ldagi barcha bekatlar (ikki uchi ham) yuklari yig‘indisi.

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida a₁ … aₙ, keyin n − 1 ta qirra. Keyin q, so‘ng q ta amal.

Chiqish ma’lumotlari

Har 2-turdagi amalga alohida qatorda javob.

Cheklovlar

1 ≤ n, q ≤ 2·10⁵; 0 ≤ aᵢ, x ≤ 10⁹. Javob 64 bitli.

1-misol: 4 → 2 → 1 → 3 yo‘lida 4 + 2 + 1 + 3 = 10; 1-bekatda yuk 100 bo‘lgach — 109.