Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | plimbare3.in, plimbare3.out | Sursă | Lot Deva 2013 - Baraj 3 Seniori |
| Autor | Andrei Parvu | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plimbare3
“Walking through the city […] I just have to find my way”
MIron, plictisit de viaţa de zi cu zi, a hotărât să iasă la plimbare în oraşul său natal, Deva. Acesta are o structură de arbore (graf neorientat aciclic conex), fiind format din N pieţe şi N–1 străzi ce le conectează. MIron doreşte să îşi aleagă o piaţă din care să îşi înceapă plimbarea, şi să parcurgă un drum cât mai lung în oraş, fără să treacă prin aceeaşi piaţă de două ori (pentru a nu se plictisi şi mai mult).
Deoarece MIron este prieten bun cu primarul oraşului, îi poate cere acestuia să mute o stradă, eliminând-o dintre pieţele pe care le conectează momentan, şi adăugând-o între alte două pieţe, astfel încât să se menţină proprietatea de arbore a oraşului Deva.
Ştiind că MIron poate apela la primar pentru mutarea unei singure străzi, voi trebuie să determinaţi lungimea maximă pe care o poate avea drumul lui MIron.
Deoarece MIron nu ştie pe care stradă să o ceară mutată, el vrea să afle lungimea maximă a drumului ce se poate forma pentru fiecare din cele N-1 cereri posibile.
Date de intrare
Pe prima linie a fişierului plimbare.in se află un număr întreg N, reprezentând numărul de pieţe din oraşul Deva.
Pe următoarele N-1 linii se află descrise străzile oraşului, fiecare din aceste linii fiind formate din două numere x şi y reprezentând faptul că există o stradă între pieţele x şi y.
Date de ieşire
Fişierul de ieşire plimbare.out va conţine N-1 linii. Pe cea de-a i-a din aceste linii se află lungimea drumului maxim dacă s-ar muta cea de-a i-a stradă din fişierul de intrare.
Restricţii
1 <= N <= 200.000
1 <= x, y <= N
Lungimea drumului între două pieţe reprezintă numărul de străzi ce trebuie parcurse pentru a ajunge dintr-o piaţă în cealaltă, fără a trece printr-o piaţă de mai multe ori.
Exemplu
| plimbare3.in | plimbare3.out |
|---|---|
| 5 1 2 1 3 4 3 5 3 | 3 4 4 4 |
Explicaţie
Putem lăsa strada (1,2) la locul ei, obţinând drumul (2,1,3,4).
Strada (1,3) se poate muta între pieţele 2 şi 4, obţinându-se drumul (1,2,4,3,5).
Strada (4,3) se poate muta între pieţele 5 şi 4, obţinându-se drumul (2,1,3,5,4).
Strada (5,3) se poate muta între pieţele 4 şi 5, obţinându-se drumul (2,1,3,4,5).
