Fișierul intrare/ieșire: diametru.in, diametru.out Sursă ad-hoc
Autor din folclor Adăugată de Catalin.FrancuCătălin Frâncu Catalin.Francu
Timp execuție pe test 0.33 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii