TractoMarm

tractomarm

== include(page="template/taskheader" task_id="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!

Poveste şi cerinţă...

h2. 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 întrebă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?_").

Fişierul de intrare $tractomarm.in$ ...

h2. Date de ieşire

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

În fişierul de ieşire $tractomarm.out$ ...

h2. 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!

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. tractomarm.in |_. tractomarm.out |

| 6
1 2
1 3
2 4
4 5
4 6
3
2 3
3 6
1 6
| 10
9
8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="tractomarm") ==

5105