Riremito

riremito

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

'Dragon Quest':https://en.wikipedia.org/wiki/Dragon_Quest, un joc clasic de tip RPG va pune la dispozitie un caracter numit Hero cu care sa explorati, sa va bateti cu monstri si sa gasiti comori. De cele mai multe ori comorile sunt ascunse in pesteri si labirinturi care se pot descrie sub forma unor arbori cu costuri pe muchii.Fanii inraiti joaca de nenumarate ori aceste jocuri si dupa o vreme ajung la eficienta maxima, acel moment in care petrec minimul de timp necesar pentru a gasi toate comorile din joc. Ce ii ajuta pe ei pentru a se plimba repede in vizita unui labirint este o vraja foarte puternica numita *Riremito*. Aceasta vraja il teleporteaza pe jucator instantaneu la intrare, acesta astfel economisind foarte mult timp necesar in plimbarea prin labirinturi.
 
Producatorii deja obisnuiti cu acesti jucatori incearca din rasputeri sa le prelungeasca timpul de joc acestor fani, pentru ca ei sa nu se plictiseasca prea repede. Deja au primit planul labirinturilor de la designeri si nu mai pot schimba cum arata acestea, insa pot alege intrarea in labirint dintr-un numar restrans de puncte. Ei se intreaba pentru fiecare din aceste puncte posibile de intrare care ar fi costul de vizitare al intregului arbore (jucatorii fiind obligati sa faca asta pentru a descoperi toate comorile).

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $riremito.in$ va contine pe prima linie $N$ numarul de noduri al arborelui ce descrie labirintul.
Urmatoarele $N - 1$ linii vor descrie muchiile arborelui fiecare pe o linie. Astfel pe fiecare linie se vor gasi $3$ numere intregi $x$, $y$ si $z$ cu semnificatia ca exista o muchie de la nodul cu indice $x$ la nodul cu indice $y$ si care poate fi traversata in $z$ secunde.
Pe urmatorul rand se va afla un numar $K$ care reprezinta numarul de noduri posibile unde ar putea fi amplasat inceputul in labirint, iar pe urmatorul rand se vor afla cele $K$ numere reprezantand indicii nodurile unde ar putea fi amplasat inceputul.

Fişierul de intrare $riremito.in$ ...

h2. Date de ieşire

În fişierul de ieşire $riremito.out$ trebuie sa se gaseasca $K$ randuri, cate unul pentru fiecare din cele $K$ noduri din fisierul de intrare reprezentand timpul minim de vizitare al intregului arbore cu intrarea fixata in fiecare din cele $K$ noduri.

În fişierul de ieşire $riremito.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 100.000$
* $1 ≤ x, y ≤ N$
* $1 ≤ z ≤ 1.000.000.000$
* *Riremito este instantaneu si poate fi folosit de oricate ori*
* $1 ≤ K ≤ 10$
* $Pentru 30% din punctaj N ≤ 20$

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

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

| 5
2 4 3
5 3 2
4 1 2
5 4 3
2
4 5
| 10
12

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

|

h3. Explicaţie
 
...

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