== 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 pv). 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˘a ˆı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 ru. 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˘aspunsuri modulo 109 + 7.
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^9^ + 7$.
h2. Date de intrare
Fişierul de intrare $arboras.in$ ...
Î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 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") ==
