Fişierul intrare/ieşire:capitala.in, capitala.outSursăLista lui Francu
AutorCatalin FrancuAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Capitala

Imperiul Roman a crescut foarte mult si este subrezit. In orice moment pot izbucni rascoale in oricare din orasele sale. Roma nu mai este o capitala sigura si Cezarul doreste sa mute capitala tarii si toate trupele imperiale intr-un oras din care armatele sa poata strabate imperiul cat mai repede; cu alte cuvinte, in orasul pentru care suma distantelor la toate celelalte orase este minima. Imperiul are N orase numerotate de la 1 la N, iar reteaua de drumuri are forma arborescenta, pentru ca armatele imperiale sa nu aiba dificultati in alegerea traseului intre doua orase. Distanta intre oricare doua orase legate printr-un drum direct este de o zi de mers.

Date de intrare

Pe prima linie a fisierului capitala.in se va afla numarul N cu semnificatia din enunt. Pe urmatoarele N-1 linii se vor afla cate doua numere A B cu semnificatia ca intre orasele A si B exista o strada.

Date de iesire

Pe prima linie a fisierului capitala.out afisati orasul in care ar trebui pusa capitala si suma distantelor pana la celelalte orase.

Restrictii

  • 1 ≤ N ≤ 200 000
  • Daca sunt mai multe posibilitati de a aseza capitala, afisati oricare dintre acestea
  • Nu se vor acorda punctaje partiale

Exemplu

capitala.incapitala.out
5
2 5
2 1
1 3
4 2
2 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content