Fişierul intrare/ieşire:	tractomarm.in, tractomarm.out	Sursă	Algoritmiada 2011, Runda 1
Autor	Andrei Parvu, Tiberiu Savin	Adăugată de	Andrei Parvu •andrei.12
Timp execuţie pe test	0.6 sec	Limită de memorie	66048 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

TractoMarm

Toată lumea îl ştie pe TractoMarm, tractoristul suprem, cel care bagă comenzi in Vim mai repede decât pot alţii să citească. Zilele trecute, TractoMarm a dat dat peste următoarea problemă: fiind dat un arbore (graf conex aciclic) cu N noduri, el ar dori să alfe suma distanţelor minime de la nodul 1 la toate celelalte noduri. Mai mult decât atât, el îşi pune M întrebări de forma: Dacă aş adăuga o muchie între x şi y în arborele meu (astfel formându-se un ciclu, şi posibil modificându-se nişte distanţe), care ar fi noua sumă a distanţelor minime de la nodul 1 la celelalte?
Deoarece această problemă nu este un tractor suficient de mare pentru TractoMarm, el s-a decis să v-o dea vouă spre rezolvare!

Date de intrare

Fişierul de intrare tractomarm.in conţine pe prima linie numărul întreg N, numărul de noduri din arbore.
Pe următoarele N - 1 linii se află perechi de numere a şi b separate prin spaţiu, semnificând că există o muchie între a şi b în arbore.
Pe următoarea linie se află M, numărul de înterbări ale lui TractoMarm.
În continuare, pe M linii, se află câte două numere x şi y, reprezentând o întrebare a lui TractoMarm la care voi trebuie să raspundeţi ("Dacă aş adăuga o muchie de la x la y în arbore care ar fi suma distaţelor minime de la nodul 1 la celelalte noduri?").

Date de ieşire

În fişierul de ieşire tractomarm.out va conţine M linii, câte una pentru fiecare înterbare din fişierul de intrare.

Restricţii

• 3 ≤ N ≤ 250000
• 1 ≤ M ≤ 400000
• 1 ≤ x, y, a, b ≤ N
• Atentie! TractoMarm vă aminteşte că memoria disponibilă pentru stivă este de maxim 8 MB!

Exemplu

Cum se trimit solutii?