| Fişierul intrare/ieşire: | capitala.in, capitala.out | Sursă | Lista lui Francu |
| Autor | Catalin Francu | Adăugată de |  Savin Tiberiu •devilkind |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | capitala.out |
|---|---|
| 5 2 5 2 1 1 3 4 2 | 2 5 |
