Fişierul intrare/ieşire: | diametru.in, diametru.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.33 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Diametru (clasele 11-12)
Se dă un arbore neorientat cu N noduri numerotate de la 1 la N. Să se găsească un diametru al arborelui, adică o cale care nu conţine niciun nod de două ori şi care are lungimea maximă (exprimată în număr de muchii).
Date de intrare
Fişierul de intrare diametru.in conţine pe prima linie numărul de noduri, N. Pe următoarele N - 1 linii se află câte o pereche de noduri u v indicând că între nodurile u şi v există o muchie.
Date de ieşire
În fişierul de ieşire diametru.out se va tipări, pe prima linie, diametrul D. Pe a doua linie se vor tipări D + 1 noduri distincte care, parcurse în ordine, formează o cale de D muchii. Dacă există mai multe soluţii, oricare este acceptabilă.
Restricţii
- 2 ≤ N ≤ 100.000
Exemplu
diametru.in | diametru.out |
---|---|
7 3 1 1 5 1 2 2 7 2 6 7 4 | 4 3 1 2 7 4 |
Explicaţie
Alte răspunsuri acceptabile ar fi fost (4 7 2 1 3), (5 1 2 7 4) sau (4 7 2 1 5), toate de 4 muchii.