==Include(page="template/taskheader" task_id="asmin")==
==Include(page="template/raw")==
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~$}.
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.
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. Date de Intrare
Pe prima linie a fisierului de intrare asmin.in se afla 2 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.
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 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.
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. Restrictii si precizari
. 2 <= N <= 16.000
. 2 <= K <= 1.000
. 0 <= R[i] <= K-1
* $2 ≤ N ≤ 16.000$
* $2 ≤ K ≤ 1.000$
* $0 ≤ R{~i~} ≤ K-1$
h2. Exemplu
asmin.in asmin.out Explicatie
5 3 5 2 Valorile asociate varfurilor celor doi arbori sunt urmatoarele:
1 2 1 5 V[1]=0 V[2]=1 V[3]=2 V[4]=0 V[5]=2
1 3 V[1]=2 V[2]=1 V[3]=2 V[4]=0 V[5]=0
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")==
