capitala

Capitala

== include(page="template/taskheader" task_id="capitala") ==

Poveste si cerinta...

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.

h2. 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.

h2. 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.

h2. Restrictii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. capitala.in |_. capitala.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

| 5
2 5
2 1
1 3
4 2| 2 5 |

== include(page="template/taskfooter" task_id="capitala") ==

2193