== include(page="template/taskheader" task_id="arboras") ==
Magul Roxanne, după nenumărate ore de cercetare a misterelor antice, a decis să meargă la cafenea să serelaxeze. Când a ajuns la vechea cafenea, a văzut pe perete o structură ciudată numită arbore. Formal, un arbore este o colect, ie 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 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.
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 ru 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˘a 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^9^ + 7$.
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^9^ + 7$.
h2. 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{~1~}, p{~2~}, . . . , 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{~1~}, d{~2~}, . . . , d{~N−1~}$, unde $d{~v~}$ este lungimea muchiei dintre vârful $v$ şi $p{~v~}$.
A doua linie conţine $N−1$ numere întregi: $p{~1~}, p{~2~}, . . . , 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{~1~}, d{~2~}, . . . , 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{~v{~i~}~}$ creşte cu $add{~i~}$.
.
h2. Date de ieşire
În fişierul de ieşire $arboras.out$ ...
Î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^9^ + 7$*.
h2. 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^9^$ 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^9^$ pentru orice $1 ≤ i ≤ Q$
h2. Exemplu
table(example). |_. arboras.in |_. arboras.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
0 0 1 1
0 0 0 0
10
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
4 1000
2 1000
|0
2
4
8
10
12
13
14
15
2015
3015
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="arboras") ==
