== 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ă 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, 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$.
h2. Date de intrare
