| Fişierul intrare/ieşire: | cuba.in, cuba.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | Chichirim George | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.65 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cuba
Marele afacerist si artist, Sorin Pastrama, dorste sa isi petreaca vacanta de primavara in Cuba. Tara arata ca un arbore cu N noduri, fiecare muchie avand o lungime (acestea sunt bidirectionale). In fiecare nod se afla benzinarii (de la care iti poti face plinul) si, de asemenea, pe fiecare muchie exista o masina electrica care poate cara o cisterna cu combustibil cu scopul de a-l ajuta pe domnul Pastrama sa traverseze muchia cu bine. Costul de a inchiria o astfel de masina electrica care sa care x unitati de combustibil este de x2. Cu scopul de a-si planui calatoria, Pastrama va cere ajutorul si va roaga sa raspundeti la Q query-uri de forma:
- X Y C -> care este costul minim pe care Pastrama trebuie sa-l plateasca firmei care inchiriaza acele masini electrice daca el doreste sa plece din nodul X si sa ajunga in nodul Y, avand la dispozitie un Mercedes cu rezervorul de capacitate C unitati de combustibil? (anumite muchii vor avea lungimea mai mare ca C, asadar pe aceste muchii masina electrica de o anumita capacitate va fi inchiriata)
Date de intrare
Fişierul de intrare cuba.in contine pe prima linie numerele naturale N si Q, cu semnificatiile din enunt. Pe urmatoarele N-1 linii se afla cate doua numere naturale Ti si Li care reprezinta tatal nodului i si lungimea muchiei respective (2 ≤ i ≤ N). Radacina arborelui este nodul 1. Pe urmatoarele Q linii se afla cate 3 numere X Y C, cu semnficatiile din enunt.
Date de ieşire
Fişierul de ieşire cuba.out contine Q linii, pe fiecare linie aflandu-se raspunsul la cate un query, in ordinea in care acestea apar in fisierul de intrare.
Restricţii
- 1 ≤ N, Q ≤ 105
- 1 ≤ Li, C ≤ 105
- 1 ≤ X, Y ≤ N
- Pentru a parcurge o distanta de lungime x, sunt necesare x unitati de combustibil.
- Oricat de mult si-ar dori Pastrama sa isi petreaca cat mai mult timp cu soferita cubaneza a masinii electrice, acesta vrea sa isi pastreze banii ca sa mearga si prin alte tari straine.
Exemplu
| cuba.in | cuba.out |
|---|---|
| 5 3 1 4 1 5 2 1 2 3 5 3 4 2 3 2 4 5 3 | 1 13 0 |
Explicaţie
Primul query: Rezervorul de capacitate 4 este de ajuns pentru muchiile 5 -> 2 si 2 -> 1, dar nu este de ajuns pentru muchia 1 -> 5. Pentru aceasta muchie este nevoie de inca o unitate de combustibil in plus. Deci, costul este 12 = 1.
Al doilea query: Pentru muchiile 2 -> 1 si 1 -> 5 sunt necesare inca 2, respectiv 3 unitati de combustibil. Deci, costul este 22 + 32 = 13.
Al treilea query: Rezervorul de capacitate 3 este de ajuns pentru fiecare muchie de pe drumul de la nodul 4 la nodul 5. Deci, costul este 0.
