Fişierul intrare/ieşire:	arboras.in, arboras.out	Sursă	RMI 2020 Ziua 2
Autor	Andrei Constantinescu, Dan Constantin Spatarel, Tamio-Vesa Nakajima	Adăugată de	Bogdan Pop •Bodo171
Timp execuţie pe test	1.75 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Arboras

Magul Roxanne, după nenumărate ore de cercetare a misterelor antice, a decis să meargă la cafenea să se relaxeze. Când a ajuns la vechea cafenea, a văzut pe perete o structură ciudată numită arbore. Formal, un arbore este o colect, i.e. de N vârfuri numerotate cu numere naturale consecutive, unde vârful 0 este rădăcina, şi toate celelalte vârfuri au un părinte unic (vârful v are părintele p_v). Deoarece cafeneaua este condusă de magi şi programatori, arborele este desenat cu rădăcina în sus.

Magul, intrigat de această structură, decide să toarne cafea magică într-unul dintre vârfuri. Dacă cafeua este turnată în vârful u, atunci aceasta se revarsă în subarborele cu rădăcina în vârful u. Deoarece este o cafea magică, nu curge la întâmplare ci ocupă cel mai lung lanţ, pe care îl poate ocupa, în subarborele cu rădăcina în vârful u, când trece prin nodul u. Cantitatea de cafea pierdută când curge, este proporţională cu lungimea lanţului pe care cafeaua îl ocupă. Roxanne notează această cantitate cu r_u. Reţineţi că muchiile arborelui pot avea lungimi diferite.

Roxanne este interesată de cantitatea de cafea pe care ar putea să o piardă dacă o toarnă în toate vârfurile arborelui, aceasta este suma valorilor r_u din toate vârfurile u ale arborelui. Asta nu este greu de calculat iniţial, dar programatorii decid să o provoace şi cresc lungimea anumitor muchii de Q ori. O poţi ajuta pe Roxanne să găsească lungimea totală a tuturor lanţurilor ocupate de cafea, dacă cafeua este turnată în toate vârfurile, iniţial şi după fiecare din cele Q modificări? Atenţie! Are nevoie de răspunsuri modulo 10⁹ + 7.

Date de intrare

În fişierul de intrare arboras.in, prima linie conţine un singur număr întreg N, numărul de vârfuri.
A doua linie conţine N−1 numere întregi: p₁, p₂, . . . , p_N−1, unde p_v este părintele nodului v, în timp ce nodul 0 este rădăcina.
A treia linie cont, ine N−1 numere întregi: d₁, d₂, . . . , d_N−1, unde d_v este lungimea muchiei dintre vârful v şi p_v.
A patra linie conţine Q, numărul de creşteri.
Fiecare din următoarele Q linii conţine câte două numere întregi v_i şi add_i, reprezentând modificarea i lungimea muchiei dintre vârfurile v_i şi p_vi creşte cu add_i.

Date de ieşire

În fişierul de ieşire arboras.out, tipăriţi Q+1 linii: pe linia i+1 - a afişaţi răspunsul după a i-a modificare. Pe prima linie trebuie să afişaţi răpunsul înainte de orice modificare. Toate răspunsurile trebuie afişate modulo 10⁹ + 7.

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ Q ≤ 100 000
• 1 ≤ d_i ≤ 100 000 pentru orice 1 ≤ i ≤ N-1
• 1 ≤ d_i < i pentru orice 1 ≤ i ≤ N-1
• 1 ≤ add_i ≤ 10⁹ pentru orice 1 ≤ i ≤ Q
• Pentru 11 puncte: 1 ≤ N ≤ 1 000, 1 ≤ Q ≤ 1 000
• Pentru alte 13 puncte: Intaltimea arborelui este cel mult 50
• Pentru alte 31 de puncte d_i = 100 000 pentru orice 1 ≤ i ≤ N-1, add_i = 10⁹ pentru orice 1 ≤ i ≤ Q

Exemplu

Cum se trimit solutii?