== include(page="template/taskheader" task_id="asmin") ==
==Include(page="template/taskheader" task_id="asmin")==
Poveste ...
Se considera un arbore (graf conex aciclic) cu $N$ varfuri, fara radacina fixata. Drept radacina, poate fi ales oricare dintre varfuri. Sa presupunem ca a fost ales varful cu numarul {$T$}. Intre oricare varf si $T$ exista un drum unic care contine fiecare varf al arborelui cel mult o singura data (un drum intre varfurile $i$ si $j$ este o secventa de varfuri, care incepe cu {$i$}, se termina cu {$j$}, iar intre oricare doua varfuri consecutive exista o muchie in arbore). Fiecarui varf {$i$}(inclusiv {$T$}) trebuie sa i se asocieze o valoare {$V{~i~}$}, mai mare sau egala cu {$0$}, astfel incat suma valorilor varfurilor de pe drumul dintre $i$ si radacina {$T$}, impartita la {$K$}, sa dea restul {$R{~i~}$}. Se defineste costul arborelui cu radacina fixata in {$T$}, {$C{~T~}$}, ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor $V{~i~}$ care respecta conditia precizata anterior, se va alege aceea pentru care $C{~T~}$ este minim.
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful {$S$}(diferit de {$T$}), $C{~S~}$ nu este neaparat egal cu {$C{~T~}$}.
h2. Cerinta
...
Dandu-se un arbore cu $N$ varfuri, un numar intreg $K$ si valorile {$R{~i~}$}, {$i=1,2,..,N$}, corespunzatoare fiecarui varf, determinati acele varfuri $T$ care pot fi alese drept radacina, pentru care costul $C{~T~}$ este minim (adica {$C{~T~} ≤ C{~S~}$}, oricare ar fi $S$ diferit de {$T$}), precum si costul respectiv.
h2. Restrictii
h2. Date de Intrare
...
Pe prima linie a fisierului de intrare $asmin.in$ se afla doua valori intregi: $N$ si {$K$}. Pe urmatoarele $N-1$ linii se afla cate doua numere intregi {$a b$}, separate printr-un spatiu, avand semnificatia ca exista muchie intre varfurile $a$ si {$b$}. Varfurile sunt numerotate de la $1$ la {$N$}. Pe urmatoarea linie se afla $N$ numere intregi, reprezentand valorile {$R{~i~}$}, {$i=1,2,..,N$}.
h2. Date de intrare
h2. Date de Iesire
...
Pe prima linie a fisierului de iesire $asmin.out$ se vor afisa doua valori intregi: $C$ si {$M$}. $C$ reprezinta costul minim posibil al arborelui. $M$ reprezinta numarul de varfuri care pot fi alese drept radacina si pentru care se obtine costul {$C$}. Pe a doua linie se afla $M$ numere intregi separate prin cate un spatiu, scrise in ordine crescatoare, reprezentand numerele varfurilor ce pot fi alese ca radacina astfel incat sa se obtina costul {$C$}.
h2. Date de iesire
h2. Restrictii si precizari
...
* $2 ≤ N ≤ 16.000$
* $2 ≤ K ≤ 1.000$
* $0 ≤ R{~i~} ≤ K-1$
h2. Exemplu
| asmin.in | asmin.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. asmin.in |_. asmin.out |
| 5 3
1 2
1 3
2 4
2 5
0 1 2 1 0
| 5 2
1 5
|
h3. Explicatii
Valorile asociate varfurilor celor doi arbori sunt urmatoarele:
$V{~1~}=0 V{~2~}=1 V{~3~}=2 V{~4~}=0 V{~5~}=2$
$V{~1~}=2 V{~2~}=1 V{~3~}=2 V{~4~}=0 V{~5~}=0$
== include(page="template/taskfooter" task_id="asmin") ==
==Include(page="template/taskfooter" task_id="asmin")==
