arborex

Arborex

== include(page="template/taskheader" task_id="arborex") ==

Liceul X, cel mai bun liceu de informatică din România, începe să facă experimente pentru a optimiza experienţa educaţională. Desigur, fiind un liceu specializat în informatică, cele $N$ săli de clasă din liceu sunt dispuse sub forma unui arbore, ele fiind legate prin $N - 1$ coridoare bidirecţionale astfel încât să se poată ajunge de la oricare sală la oricare alta. Renumiţii profesori ai liceului au realizat că eficienţa în educaţie depinde atât de numărul de săli de clasă, cât şi de numărul maxim de coridoare ce se leagă de câte o clasă. Mai exact, profesorii sunt interesaţi de următoarea informaţie: pentru fiecare $K$ de la $1$ la $N$, care este marimea celei mai mari submulţimi de clase conexe pe care le-am putea selecta, astfel încat nicio clasă din submulţime să nu fie legată direct de mai mult de $K$ alte clase din submulţime.

_Liceul X, cel mai bun liceu de informatică din România, începe să facă experimente pentru a optimiza experienţa educaţională. Desigur, fiind un liceu specializat în informatică, cele $N$ săli de clasă din liceu sunt dispuse sub forma unui arbore, ele fiind legate prin $N - 1$ coridoare bidirecţionale astfel încât să se poată ajunge de la oricare sală la oricare alta. Renumiţii profesori ai liceului au realizat că eficienţa în educaţie depinde atât de numărul de săli de clasă, cât şi de numărul maxim de coridoare ce se leagă de câte o clasă. Mai exact, profesorii sunt interesaţi de următoarea informaţie: pentru fiecare $K$ de la $1$ la $N$, care este marimea celei mai mari submulţimi de clase conexe pe care le-am putea selecta, astfel încat nicio clasă din submulţime să nu fie legată direct de mai mult de $K$ alte clase din submulţime._

Mai formal, se dă un arbore $A$ cu $N$ noduri. Definim un subarbore al lui $A$ ca fiind o submulţime conexă de noduri $S$. Pentru un subarbore oarecare $S$ al lui $A$, definim gradul unui nod $x$ din $S$ faţă de $S$ ca fiind numărul de noduri din $S$ de care este $x$ legat direct prin muchii. Definim gradul subarborelui $S$ ca fiind maximul gradelor nodurilor din $S$ (faţă de $S$). Se cere să calculaţi, pentru $K = 1, 2, ..., N$, mărimea maximă a unui subarbore al lui $A$ de grad cel mult K.

h2. Restricţii

* $1 < N < 200.000$
* Pentru ... puncte, $N < 2.000$.
* Pentru alte ... puncte, $N < 100.000$ şi cel mult $2.000$ de noduri sunt vecine cu mai mult de 2 noduri.
* Pentru alte ... puncte, $N < 70.000$.

* $1 ≤ N ≤ 200.000$
* Pentru 13 puncte, $N ≤ 2.000$.
* Pentru alte 15 puncte, $N ≤ 100.000$ şi cel mult $2.000$ de noduri sunt vecine cu mai mult de 2 noduri.
* Pentru alte 38 puncte, $N ≤ 70.000$.

h2. Exemple