Fişierul intrare/ieşire:arborex.in, arborex.outSursăad-hoc
AutorTamio-Vesa NakajimaAdăugată dearhivedescarc •arhive
Timp execuţie pe test1 secLimită de memorie512000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

Date de intrare

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.

Date de ieşire

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.

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.

Exemple

arborex.inarborex.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?