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 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? (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 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

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.
• 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

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 1² = 1.
Al doilea query: Pentru muchiile 2 -> 1 si 1 -> 5 sunt necesare inca 2, respectiv 3 unitati de combustibil. Deci, costul este 2² + 3² = 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.

Cum se trimit solutii?