Fişierul intrare/ieşire:tractomarm.in, tractomarm.outSursăAlgoritmiada 2011, Runda 1
AutorAndrei Parvu, Tiberiu SavinAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.6 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultateN/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 î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?").

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.

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

tractomarm.intractomarm.out
6
1 2
1 3
2 4
4 5
4 6
3
2 3
3 6
1 6
10
9
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content