Revizia anterioară Revizia următoare
| 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 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!
Date de intrare
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?").
Date de ieşire
În fişierul de ieşire tractomarm.out contime M linii, cate una pentru fiecare interbare din fisierul de intrare.
Restricţii
- 3 ≤ N ≤ 250000
- 1 ≤ M ≤ 400000
- 1 ≤ x, y, a, b ≤ N
Exemplu
| tractomarm.in | tractomarm.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
