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. 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 x². 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 ≤ 10⁵
• 1 ≤ L _i, C ≤ 10⁵
• 1 ≤ X, Y ≤ N
• Pentru a parcurge o distanta de lungime x, sunt necesare x unitati de combustibil.

Exemplu

Explicaţie

...

Cum se trimit solutii?