Fişierul intrare/ieşire:maxdist.in, maxdist.outSursăLot Focsani 2016, Baraj 1 Seniori
AutorRadu Visan, Stefan PopaAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test1.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Maxdist

Oraşul Focşani este organizat sub forma unui arbore cu N noduri, fiecare nod reprezentând un cartier al acestui oraş. În Focşani, există o bandă de biciclişti care se plimbă în voie prin oraş. Într-o zi, o altă bandă de biciclişti îşi face apariţia în Focşani şi începe să cucerească, câte unul pe zi, o parte din cartierele ce mai demult aparţineau primei bande de biciclişti. La finalul unei zile, bicicliştii din ambele bande pornesc dintr-un cartier pe care îl deţin şi se deplasează spre un alt cartier pe care îl deţin, fără a trece de mai multe ori prin acelaşi cartier. Întrucât bicicliştii din Focşani sunt foarte try-hard, aceştia îşi doresc sa parcurgă o distanţă cât mai lungă în fiecare zi. Astfel, după fiecare zi în care unul din cartierele primei benzi este cucerit de a doua bandă, fiecare bandă se întreabă care e distanţa maximă care se poate parcurge, alegând convenabil cartierul de pornire si cel destinaţie, dintre cele pe care banda le deţine.

Cerinta

Cunoscându-se structura oraşului Focşani, un număr Q de zile şi ce cartier este cucerit de a doua bandă în fiecare din cele Q zile, se cere distanţa maximă pe care fiecare bandă o poate parcurge în cele Q zile. Se consideră că, într-o zi, mai întâi are loc cucerirea unui cartier şi apoi deplasarea bicicliştilor.

Date de intrare

Pe prima linie a fişierului de intrare maxdist.in se vor afla două numere naturale N si Q, reprezentând numărul de cartiere din Focşani, respectiv numărul de zile care ne interesează. Pe următoarele N – 1 linii, se vor afla câte două numere naturale x şi y, reprezentând faptul că există o muchie între x şi y. Pe următoarele Q linii, se va afla câte un număr natural c, care reprezintă cartierul cucerit de a doua bandă în ziua respectivă.

Date de ieşire

Fişierul de ieşire maxdist.out va conţine Q linii. Pe linia i, se vor afişa două numere naturale, reprezentând distanţa maximă pe care o pot parcurge membrii din prima bandă, respectiv a doua bandă, după ziua i.

Restricţii

  • 2 ≤ N ≤ 200000
  • 1 ≤ Q ≤ N
  • 1 ≤ x, y, c ≤ N
  • Un cartier va fi cucerit o singură dată.
  • Distanţa dintre două cartiere este definită ca numărul de muchii dintre acestea.
  • Dacă nu există cel puţin două cartiere deţinute de o bandă, vom considera că distanţa maximă pe care această bandă o poate parcurge este 0.
  • Bicicliştii pot trece prin cartiere ce nu aparţin bandei lor, dar nu pot să plece din acestea sau să se oprească în acestea.
  • Pentru 20% din teste, N ≤ 1000.
  • Pentru restul de 80% din teste, 100000 ≤ N ≤ 200000.

Exemplu

maxdist.inmaxdist.out
10 6
1 2
2 3
2 8
3 4
3 5
1 6
6 7
6 9
1 10
3
6
4
5
10
9
5 0
5 3
5 4
4 4
4 4
4 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?