Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-19 17:34:46.
Revizia anterioară   Revizia următoare  

 

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 test0.65 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. In fiecare nod se afla benzinarii 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.

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 T i si L i 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

În 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 ≤ L i, C ≤ 105
  • 1 ≤ X, Y ≤ N
  • Pentru a parcurge o distanta de lungime x, sunt necesare x unitati de combustibil.

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

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?