| Fişierul intrare/ieşire: | zelda.in, zelda.out | Sursă | Algoritmiada 2022, Runda 4 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Rapeanu George •georgerapeanu |
| Timp execuţie pe test | 0.9 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zelda
Legătură, eroul legendei, trebuie sa cucerească castelul unui vrăjitor malefic! Ajunge într-o încăpere misterioasă, în care vede un mecanism complicat. Mecanismul ia forma unui arbore cu n noduri, unde fiecare muchie are un cost întreg. La diverse momente, lungimile muchiilor arborelui se modifică.
După câteva ore de încercări nereuşite, Legătură îşi dă seama că, pentru a putea trece de încăpere, va trebui să calculeze costul de comprimare (definit mai jos) a mai multor lanţuri din arbore. Mai exact, Legătură are q interogări de două tipuri. Pentru fiecare interogare, fie Legătură observă ca se modifică lungimea unei muchii, fie el vrea să afle costul de comprimare al unui lanţ. Puteţi să-l ajutaţi pe Legătură să rezolve toate interogările?
Costul de comprimare. Costul de comprimare al unui lanţ se calculează în felul următor: se identifică toate nodurile din lanţ, apoi se calculează suma lungimilor tuturor lanţurilor din arborele ce rezultă. De exemplu, dacă considerăm arborele cu 6 noduri şi muchiile (1, 2), (2, 3), (4, 5), (5, 6), (2, 5), toate cu costul 1, şi vrem să calculăm costul de comprimare al lanţului de la 1 la 6, mai întâi identificăm toate nodurile din lanţul 1, 2, 5, 6, arborele devenind astfel unul cu 3 vârfuri, şi muchiile (4, 1), (1, 3). Apoi, calculăm suma lungimilor tuturor lanţurilor din arbore. Suma aceasta este 4, căci sunt 3 lanţuri cu lungimea 0, 2 cu lungimea 1 şi 1 cu lungimea 2. Atenţie! Arborele nu se modifică după ce se calculează un cost de comprimare.
Date de intrare
Fişierul de intrare zelda.in va conţine pe prima linie numărul n cu semnificaţia din enunţ, urmate de n - 1 linii, fiecare conţinând 3 numere x y z, cu semnificaţia că există o muchie între nodurile x şi y cu lungimea z.
Pe următoarea linie se va afla numărul q, urmat de q linii, fiecare având una dintre următoarele forme:
- 0 x y z, ce reprezintă operaţia de update, cu semnficaţia că lungimea muchiei dintre nodurile x şi y devine z
- 1 x y, ce reprezintă operaţia de query, pentru care trebuie calculat costul de comprimare al lanţului dintre nodurile x şi y, modulo 1000000007
Date de ieşire
Fişierul de ieşire zelda.out va conţine un număr de linii egal cu numărul de query-uri, fiecare linie conţinând răspunsul query-ului său.
Restricţii
- 2 ≤ n ≤ 100000
- 1 ≤ q ≤ 100000
- 1 ≤ x, y ≤ n, pentru oricare muchie din arbore
- 0 ≤ z ≤ 1000000000, pentru oricare update/muchie din arbore
- Pentru fiecare operaţie de update, se garantează că muchia x y există în arbore
- Pentru 20 de puncte, n ≤ 100, q ≤ 200, iar inputul nu are operaţii de update
- Pentru alte 20 de puncte, inputul nu are updateuri
Exemplu
| zelda.in | zelda.out |
|---|---|
| 3 1 2 10 1 3 4 8 1 1 1 1 1 2 1 1 3 1 2 3 0 1 2 2 1 3 3 1 1 2 1 2 3 | 28 4 10 0 12 4 0 |
Explicaţie
În această explicaţie, lungime(i, j) este lungimea lanţului cu capetele în i şi j. Vom ignora lanţurile formate dintr-un singur nod, căci acestea au mereu lungimea egală cu 0.
Pentru primul query, comprimarea este aplicată asupra lanţ format dintr-un singur nod. Astfel, arborele nu se schimbă, iar costul lui este: lungime(1,2) + lungime(1,3) + lungime(2,3) = 10 + 4 + 14 = 28.
Pentru al doilea query, comprimarea este aplicată asupra lanţului 1-2. Astfel, arborele va conţine o singură muchie (cea dintre nodul 1 şi nodul 3 cu costul 4), iar costul lui devine: lungime(1,3) = 4.
Penru al treilea query, comprimarea este aplicată asupra lanţului 1-3. Astfel, arborele va conţine o singură muchie (cea dintre nodul 1 şi nodul 2 cu costul 10), iar costul lui devine: lungime(1, 2) = 10.
Pentru al patrulea query, comprimarea este aplicată asupra lanţului 2-3. Astfel, arborele va fi comprimat într-un singur nod, şi nu va avea nicio muchie rămasă, iar costul lui devine 0.
Urmează un update al muchiei de la 1 la 2, a cărei valoare devine 2.
Pentru al cincilea query, comprimarea este aplicată asupra lanţ format dintr-un singur nod. Astfel, arborele nu se schimbă, iar costul lui este: lungime(1,2) + lungime(1,3) + lungime(2,3) = 2 + 4 + 6 = 12.
Pentru al şaselea query, comprimarea este aplicată asupra lanţului 1-2. Astfel, arborele va conţine o singură muchie (cea dintre nodul 1 şi nodul 3 cu costul 4), iar costul lui devine: lungime(1,3) = 4.
Pentru al şaptelea query, comprimarea este aplicată asupra lanţului 2-3. Astfel, arborele va fi comprimat într-un singur nod, şi nu va avea nicio muchie rămasă, iar costul lui devine 0.
