Fişierul intrare/ieşire:	maxdist.in, maxdist.out	Sursă	Lot Focsani 2016, Baraj 1 Seniori
Autor	Radu Visan, Stefan Popa	Adăugată de	Vlad Dumitru-Popescu •depevlad
Timp execuţie pe test	1.5 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/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

Cum se trimit solutii?