Fişierul intrare/ieşire:asmin.in, asmin.outSursăONI 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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 Vi, 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 Ri. Se defineste costul arborelui cu radacina fixata in T, CT, ca fiind suma valorilor asociate fiecarui nod. Dintre toate posibilitatile de alegere a valorilor Vi care respecta conditia precizata anterior, se va alege aceea pentru care CT este minim.
Se constata usor ca alegand alt varf drept radacina, de exemplu, varful S(diferit de T), CS nu este neaparat egal cu CT.

Cerinta

Dandu-se un arbore cu N varfuri, un numar intreg K si valorile Ri, i=1,2,..,N, corespunzatoare fiecarui varf, determinati acele varfuri T care pot fi alese drept radacina, pentru care costul CT este minim (adica CT ≤ CS, 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 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 Ri, 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 ≤ Ri ≤ K-1

Exemplu

asmin.inasmin.out
5 3
1 2
1 3
2 4
2 5
0 1 2 1 0
5 2
1 5

Explicatii

Valorile asociate varfurilor celor doi arbori sunt urmatoarele:
V1=0  V2=1 V3=2  V4=0  V5=2
V1=2  V2=1 V3=2  V4=0  V5=0

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content