tractomarm

TractoMarm

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

Poveste şi cerinţă...

 
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 decat atat, el isi pune $M$ intrebari de forma: _Daca as adauga o muchie intre $x$ si $y$ in arborele meu (astfel formandu-se un ciclu, si posibil modificandu-se niste distante), care ar fi noua suma a distantelor minime de la nodul $1$ la celelalte?_
Deoarece aceasta problema nu este un tractor suficient de mare pentru TractoMarm, el s-a decis sa v-o dea voua spre rezolvare!

h2. Date de intrare

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

Fişierul de intrare $tractomarm.in$ contine pe prima linie numarul intreg $N$, numarul de noduri din arbore.
Pe urmatoarele N - 1 linii se afla perechi de numere $a$ si $b$ separate prin spatiu, semnificand ca exista o muchie intre $a$ si $b$ in arbore.
Pe urmatoarea linie se afla $M$, numarul de interbari ale lui TractoMarm.
In continuare, pe $M$ linii, se afla cate doua numere $x$ si $y$, reprezentand o intrebare a lui TractoMarm la care voi trebuie sa raspundeti ("_Daca as aduga o muchie de la $x$ la $y$ in arbore care ar fi suma distatelor minime de la nodul $1$ la celalte noduri?_").

h2. Date de ieşire

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

În fişierul de ieşire $tractomarm.out$ contime $M$ linii, cate una pentru fiecare interbare din fisierul de intrare.

h2. Restricţii

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

* $3$ ≤ $N$ ≤ $250000$
* $1$ ≤ $M$ ≤ $400000$
* $1$ ≤ $x$, $y$, $a$, $b$ ≤ $N$

h2. Exemplu

  multiple lines.
|

h3. Explicaţie
 
...

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