Fişierul intrare/ieşire:	asmin.in, asmin.out	Sursă	ONI 2003
Autor	Mugurel Ionut Andreica	Adăugată de
Timp execuţie pe test	0.05 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

Asmin

Asmin

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

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.

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.

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.

Restrictii si precizari

. 2 <= N <= 16.000

. 2 <= K <= 1.000

. 0 <= R[i] <= K-1

Exemplu

asmin.in asmin.out Explicatie
5 3 5 2 Valorile asociate varfurilor celor doi arbori sunt urmatoarele:

1 2 1 5 V¹=0 V²=1 V³=2 V⁴=0 V⁵=2

1 3 V¹=2 V²=1 V³=2 V⁴=0 V⁵=0

2 4

2 5

0 1 2 1 0

Cum se trimit solutii?