
			LA CULES DE ZMEURICA

	O colonie de termite a iesit la cules de zmeurica in tufa din apropierea musuroiului.
Consiliul Economic a hotarat ca aceasta tufa trebuie sa asigure hrana musuroiului atat anul
acesta, cat si anul urmator, dupa aceasta ea nemaiprezentand interes.

	Tufa de zmeurica are un aspect arborescent: din pamant pornesc, una sau mai multe
ramuri, care la randul lor se ramifica in mai multe ramurele etc. In fiecare an, in varful
fiecarei crengute care nu se mai ramifica creste cate un bob de zmeura. Pentru buna desfa-
surare a culesului, Consiliul de Supervizare a etichetat imbinarile ramurelelor si varfurile
crengutelor cu numere naturale consecutive, incepand de la 1. Radacina tufei (cea de la
contactul cu solul) are numarul 1. In figura din stanga, fructele de zmeura cresc in nodurile 
		2,5,6 si 7. 	
 5  2   7   
 |   \ /
 3  6 4
  \ / /
   1--
	Bugetul musuroiului se modifica astfel:
1)Fiecare fruct cules aduce P unitati de hrana in hambar
2)Culegerea unui fruct "en detail" inseamna trimiterea unei termite de la sol pana la acel
fruct pentru a-l taia de pe crenguta lui. Termita consuma C unitati de hrana din hambar
pentru fiecare ramurica pe care o parcurge pana la bobul de zmeura. In figura de mai sus,
culegerea fructelor 2,5 si 7 necesita consumarea a 2*c unitati de hrana, iar culegerea
fructului 6 necesita C unitati de hrana. Anul viitor, un nou bob va creste in locul celui cules.
3) Zmeurica poate fi culeasa si "en-gros", producand insa daune tufei. Este posibil ca un nod
intreg sa fie retezat,impreuna cu tot subarborele sau. Pentru aceasta va fi trimisa o termita
de la sol pana la nodul care va fi retezat, termita consumand cate C unitati de hrana pentru fiecare
ramura parcursa. Dupa aceasta, fructele de pe creanga retezata cad pe sol si sunt culese cu cost 0.
In figura de sus, retezarea nodului 4 se face cu cost 1*C si aduce un profit de 2*P (datorita
fructelor din nodurile 2 si 7). Dezavantajul este ca anul viitor in nodul retezat va creste o
singura zmeurica. Daca nodul 1 este retezat (tufa este taiata din radacina), anul viitor nu va
mai creste nimic.

	Se cere sa se planifice o maniera de culegere a zmeurei in primul si in al doilea an
astfel incat in final hambarul sa fie cat mai imbelsugat.

	DATE DE INTRARE

	Fisierul text "zmeurica.in" contine pe prima linie valorile pentru N,P si C (2<=N<=100,
1<=P,C<=1000), separate prin spatii. N este numarul total de noduri etichetate, iar P si C sunt
numere intregi. Pe urmatoarele N linii se afla descrierea tufei de zmeura. Linia k+1 contine
numarul de noduri care se afla imediat deasupra nodului k in tufa, apoi valorile acestor noduri
in ordine crescatoare. Pentru figura de mai sus fisierul este :

7 5 1				% N=7,P=5,C=1
3 3 4 6				% Dupa nodul 1(radacina) urmeaza 3 noduri : 3,4 si 6
0				% Dupa nodul 2 nu mai urmeaza nimic
1 5				% Dupa nodul 3 urmeaza 1 nod : 5
2 2 7				% Dupa nodul 4 urmeaza 2 noduri : 2 si 7
0				% Dupa nodul 5 nu mai urmeaza nimic
0				% Dupa nodul 6 nu mai urmeaza nimic
0				% Dupa nodul 7 nu mai urmeaza nimic

	DATE DE IESIRE

	Fisierul text "zmeurica.out" trebuie sa contina 3 linii. Pe prima se va afla cantitatea
maxima de hrana (venit minus cheltuieli) care poate fi acumulata din exploatarea tufei de zmeurica.
Pe linia a doua se vor indica, separate prin spatii, in orice ordine, numerele nodurilor unde se
vor face taieturi in primul an (pentru a taia fie un fruct, fie o creanga intreaga). Pe linia a
treia se vor indica nodurile unde se fac taieturi in al doilea an. Daca in al doilea an nu mai
exista nici un nod de taiat, linia a treia va fi lasata goala. Pentru exemplul dat, iesirea
poate fi:

34
3 6 2 7
1

Timp de rulare : 1 sec./test pentru 586 la 133 Mhz