Fişierul intrare/ieşire:cuba.in, cuba.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1.3 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.incuba.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?