razboi

Razboiul lumilor

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

==Include(page="template/taskheader" task_id="razboi")==

Poveste ...

Tara A are $N$ orase numerotate de la $1$ la {$N$}. Aceste orase sunt conectate prin strazi bidirectionale in asa fel incat exista exact un singur drum intre orice pereche de orase. Deoarece tara A a fost atacata de tara B, tara A vrea sa pozitioneze intr-unul din orasele ei comandamentul armatei. Din motive defensive, comandamentul trebuie plasat in orasul cu proprietatea ca maximul distantei dintre orasul ales si oricare alt oras este minima (in cazul in care un oras oarecare este atacat, comandamentul trebuie sa ajunga acolo cat mai repede posibil; folosind proprietatea de mai sus se incearca minimizarea pagubelor in cazul cel mai defavorabil).

h2. Cerinta

...

Gasiti toate orasele in care poate fi plasat comandamentul.

h2. Restrictii

h2. Data de intrare

...

Fisierul de intrare $razboi.in$ contine pe prima linie numarul $T$ de teste. Urmatoarele linii descriu cele $T$ teste. Prima linie a fiecarui test contine numarul {$N$}, reprezentand numarul de orase din tara A. Urmatoarele $N-1$ linii contin descrierea unei strazi - trei numere intregi separate prin spatii: {$A, B, D$}. $A$ si $B$ reprezinta numarul oraselor conectate de acea strada iar $D$ reprezinta lungimea strazii.

h2. Date de intrare

h2. Date de iesire

...

Pentru fiecare test afisati in fisierul $razboi.out$ urmatoarea linie: "Testul nr #{$XXX$}", unde $XXX$ reprezinta numarul testului respectiv. Afisati apoi pe urmatoarele linii numarul oraselor in care ar putea fi plasat comandamentul. Aceste numere trebuie afisate in ordine crescatoare.

h2. Date de iesire

h2. Restrictii

...

* $1 ≤ N ≤ 16000$
* $1 ≤ D ≤ 10000$
* $1 ≤ T ≤ 20$

h2. Exemplu

| razboi.in | razboi.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. razboi.in |_. razboi.out |
| 3
5
1 2 1
1 3 2
1 4 3
4 5 4
2
1 2 19
3
1 2 1
2 3 1
| Testul nr #1
4
Testul nr #2
1
2
Testul nr #3
2 |

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

==Include(page="template/taskfooter" task_id="razboi")==
 
 

575