== include(page="template/taskheader" task_id="arborex") ==
Poveste şi cerinţă...
_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. Date de intrare
Fişierul de intrare $arborex.in$ ...
Fişierul de intrare $arborex.in$ va conţine pe primul rând numărul natural $N$.
Pe următoarele $N - 1$ rânduri vor apărea perechi $a b$, ce reprezintă o muchie nedirecţionată între nodurile $a$ şi $b$.
h2. Date de ieşire
În fişierul de ieşire $arborex.out$ ...
Fişierul de ieşire $arborex.out$ va conţine $N$ rânduri. Pe rândul $i$ va apărea răspunsul pentru $K = i$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $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. Exemplu
h2. Exemple
table(example). |_. arborex.in |_. arborex.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
| 5
3 1
3 5
3 4
1 2
| 2
4
5
5
5 |
| 7
4 2
4 5
7 4
4 1
4 3
7 6
| 2
4
5
6
7
7
7 |
| 10
9 4
9 2
9 8
9 1
3 9
10 7
9 5
6 3
6 10
| 2
6
7
8
9
10
10
10
10
10 |
| 12
1 8
1 11
11 9
12 6
1 5
1 12
5 2
11 4
1 3
5 7
5 10
| 2
5
9
11
12
12
12
12
12
12
12
12 |
| 20
8 13
16 12
20 4
20 8
16 2
5 9
16 5
16 17
8 3
16 7
5 10
5 14
16 11
16 6
8 19
20 16
5 18
5 1
20 15
| 2
6
10
14
16
18
19
20
20
20
20
20
20
20
20
20
20
20
20
20 |
...
== include(page="template/taskfooter" task_id="arborex") ==
