"Dandu-se maximul M al timpilor de rezolvare, sa se infiinteze un numar minim de puncte de salvare, nu neaparat limitat de K, care sa acopere intreg arborele."

Presupunand ca putem rezolva aceasta problema, SALVAREA se rezolva cu ajutorul unei cautari binare. Incercam intai cu M=N/2, daca obtinem solutie cu cel mult K noduri vom incerca cu M=N/4, altfel cu M=3N/4 etc. Se pastreaza valoarea minima a lui M pentru care se poate obtine solutie cu cel mult K puncte de salvare. Daca se folosesc mai putin de K puncte, celelalte se vor plasa aleator.

Cum rezolvam subproblema? Ne folosim de o echivalenta a solutiilor. Presupunand ca am avea o solutie pentru un anumit arbore, in care un punct de salvare este la o distanta mai mica de M de orice frunza (aici prin "frunza" intelegem "nod de grad 1", deci nu stabilim o radacina a arborelui, toate nodurile de grad 1 se considera frunze), putem obtine una echivalenta mutand punctul respectiv "mai departe" de frunza respectiva, pana cand ajunge la distanta M de cel mult o frunza. Punctul respectiv de salvare acopera exact aceeasi multime de noduri "periferice", plus eventual cateva noi dinspre "centrul" arborelui.

Pentru a construi solutia se parcurge arborele de la frunze spre centru, astfel: se introduc frunzele intr-o coada. Cand examinam un nod din coada, scadem gradul vecinului sau cu 1. Cand un nod are gradul cel mult 1 (toti vecinii dinspre periferie au fost examinati), este introdus in coada.

La examinare, fiecare nod trimite catre centru (deci catre unicul sau vecin care mai este luat in considerare) o cerere, in care precizeaza distanta maxima la care accepta un punct de salvare. Frunzele trimit cereri cu valoarea M.

La introducerea in coada, un nod trebuie sa cunoasca valoarea cererii pe care o va trimite mai departe. Pentru aceasta, se alege valoarea minima a cererilor primite, din care se scade 1 (pentru ca distanta fata de centru a celui mai departat nod creste cu 1 prin intermediul nodului curent). Cand distanta ajunge 0, nodul respectiv este "obligat" sa devina punct de salvare. El va acoperi o raza de M inspre periferie, dar si inspre centru, deci va avea nevoie de un nou punct de salvare la distanta 2*M+1. Evident ca, datorita cererilor altor noduri, probabil ca urmatorul punct de salvare va fi plasat mai aproape.

Subproblema se rezolva liniar (de fapt sursa Comisiei nu este complet optimizata din punct de vedere al structurii de date care retine arborele, dar ruleaza suficient de rapid pe testele date).

Pentru detalii de implementare consultati sursa autorului problemei (scrisa in Borland Pascal 7.0).

{$D+,E+,I+,L+,N-,O-,P-,Q-,R-,T-,V+,X+,Y+}

{$M 16384,0,655360}

var p,opt,nr,st,en,lo,hi,med,i,j,k,kk,l,m,n,mp:longint;

fi,fo:text;

a:array[1..2003,1..2] of longint;

ok:array[1..2003] of longint;

dd,start,c,d,sol,t,x:array[1..1003]of integer;

procedure readdata;

begin

assign(fi,'salvare.in');

assign(fo,'salvare.out');

reset(fi);

readln(fi,n);

readln(fi,kk);

for l:=1 to n-1 do

begin

readln(fi,a[l,1],a[l,2]);

a[n+l-1,1]:=a[l,2];

a[n+l-1,2]:=a[l,1];

end;

close(fi);

end;

function try:boolean;

begin

try:=false;

fillchar(ok,sizeof(ok),0);

fillchar(c,sizeof(c),0);

fillchar(x,sizeof(x),0);

d:=dd;

for i:=1 to n do

t[i]:=9999;

nr:=0;

{ bag in coada frunzele si trimit in sus }

st:=1;

en:=0;

for i:=1 to n do

if d[i]=1 then

begin

inc(en);

c[en]:=i;

t[i]:=med;

end;

while en<n do

begin

{ scade gradul vecinului lui st }

{ daca acesta are gradul 0, il baga in coada }

i:=c[st];

for j:=start[i] to start[i+1]-1 do

if ok[j]=0 then

begin

ok[j]:=1;

k:=a[j,2];

break;

end;

dec(d[i]);

dec(d[k]);

if t[i]<t[k] then

t[k]:=t[i];

for j:=start[k] to start[k+1]-1 do

if a[j,2]=i then

begin

ok[j]:=1;

break;

end;

if d[k]=1 then

begin

t[k]:=t[k]-1;

if t[k]=0 then

begin

x[k]:=1;

t[k]:=2*med+1;

nr:=nr+1;

end;

inc(en);

c[en]:=k;

end;

inc(st);

end;

if nr=0 then

begin

nr:=1;

x[c[en]]:=1;

end;

if nr<=kk then

begin

try:=true;

if med<opt then

begin

opt:=med;

sol:=x;

end;

end;

end;

procedure solve;

begin

opt:=n+1;

m:=2*n-2;

for i:=1 to m do

begin

mp:=i;

for j:=i+1 to m do

if (a[j,1]<a[mp,1])or((a[j,1]=a[mp,1])and(a[j,2]<a[mp,2])) then

mp:=j;

a[m+1]:=a[mp];

a[mp]:=a[i];

a[i]:=a[m+1];

a[m+1]:=a[m+2];

end;

start[1]:=1;

j:=1;

for i:=2 to n do

begin

repeat

inc(j);

until a[j,1]=i;

start[i]:=j;

end;

start[n+1]:=m+1;

for i:=1 to n do

d[i]:=start[i+1]-start[i];

dd:=d;

{ urmeaza cautarea binara }

lo:=1;

hi:=n;

while lo<=hi do

begin

med:=(lo+hi)div 2;

if try then

hi:=med-1

else

lo:=med+1;

end;

p:=kk;

for i:=1 to n do

p:=p-sol[i];

for i:=1 to n do

if (p>0)and(sol[i]=0) then

begin

sol[i]:=1;

dec(p);

end;

if kk=n then

opt:=0;

rewrite(fo);

writeln(fo,opt);

for i:=1 to n do

if sol[i]=1 then

write(fo,i,' ');

writeln(fo);

close(fo);

end;

begin

readdata;

solve;

end.