Revizia anterioară Revizia următoare
| 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ă 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ă î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ăspunsuri modulo 109 + 7.
Date de intrare
Fişierul de intrare arboras.in ...
Date de ieşire
În fişierul de ieşire arboras.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| arboras.in | arboras.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
