Problem asmin


Se consideră un arbore (graf conex aciclic) cu N vârfuri, fără rădăcină fixată. Drept rădăcină, poate fi ales oricare dintre vârfuri. Să presupunem că a fost ales vârful cu numărul T. Între oricare vârf şi T există un drum unic care conţine fiecare vârf al arborelui cel mult o singură dată (un drum între vârfurile i şi j este o secvenţă de vârfuri, care începe cu i, se termină cu j, iar între oricare două vârfuri consecutive există o muchie în arbore). Fiecărui vârf i(inclusiv T) trebuie să i se asocieze o valoare \(V_i\), mai mare sau egală cu 0, astfel încât suma valorilor vârfurilor de pe drumul dintre i şi rădăcina T, împărţită la K, să dea restul \(R_i\). Se defineşte costul arborelui cu rădăcina fixată în T, \(C_T\), ca fiind suma valorilor asociate fiecărui nod. Dintre toate posibilităţile de alegere a valorilor \(V_i\) care respectă condiţia precizată anterior, se va alege aceea pentru care \(C_T\) este minim.
Se constată uşor că alegând alt vârf drept rădăcină, de exemplu, vârful S (diferit de T), \(C_S\) nu este neapărat egal cu \(C_T\).

Cerinţă

Dându-se un arbore cu N vârfuri, un număr întreg K şi valorile \(R_i, i=1,2,..,N\), corespunzătoare fiecărui vârf, determinaţi acele vârfuri T care pot fi alese drept rădăcină, pentru care costul \(C_T\) este minim (adică \(C_T≤C_S\), oricare ar fi S diferit de T), precum şi costul respectiv.

Date de intrare

Pe prima linie a fişierului de intrare asmin.in se află 2 valori întregi: N şi K. Pe următoarele N-1 linii se află câte două numere întregi a b, separate printr-un spaţiu, având semnificaţia că există muchie între vârfurile a şi b. Vârfurile sunt numerotate de la 1 la N. Pe următoarea linie se află N numere întregi, reprezentând valorile \(R_i, i=1,2,..,N\).

Date de ieşire

Pe prima linie a fişierului de ieşire asmin.out se vor afişa două valori întregi: C şi M. C reprezintă costul minim posibil al arborelui. M reprezintă numărul de vârfuri care pot fi alese drept rădăcină şi pentru care se obţine costul C. Pe a doua linie se află M numere întregi separate prin câte un spaţiu, scrise în ordine crescătoare, reprezentând numerele vârfurilor ce pot fi alese ca rădăcină astfel încât să se obţină costul C.

Restricţii şi precizări

  • 2 ≤ N ≤ 16000
  • 2 ≤ K ≤ 1000
  • \(0 ≤ R_i ≤ K-1\)
  • Cel puţin 40% din testele folosite la evaluare vor avea N ≤ 1000

Exemplu

asmin.in

5 3
1 2
1 3
2 4
2 5
0 1 2 1 0

asmin.out

5 2
1 5

Explicații

Cei doi arbori obţinuţi (împreună cu valorile asociate vârfurilor) sunt următorii:

General info

ID: 119

Upload: liviu

Input: asmin.in/asmin.out

Memory limit: 64MB/16MB

Time limit: 0.03s

Source: ONI 2003 XI-XII: Ziua 1 Problema 1

Submissions

Special Submissions