== include(page="template/taskheader" task_id="grarbore") ==
Poveste şi cerinţă...
Bossanip şi Henry au un arbore $A$ cu $N$ noduri. Ei se întreabă, pentru fiecare valoare $k$ cuprinsă între $1$ şi $N-1$, care este numărul de subarbori ai lui $A$ pentru care gradul maxim al unui nod din subarbore este egal cu $k$. Un subarbore se defineşte ca fiind o submulţime conexă de noduri şi muchii din arborele $A$. Gradul unui nod dintr-un subarbore se defineşte ca numărul de vecini pe care îi are acel nod în subarbore (NU în arborele $A$).
h2. Date de intrare
Fişierul de intrare $grarbore.in$ ...
Fişierul de intrare *grarbore.in* va conţine pe prima linie un număr natural $T$, semnificând numărul de arbori din fişierul de intrare. Pe liniile următoare se vor afla descrierile celor $T$ arbori. Descrierea celui de-al $i$-lea arbore va conţine pe prima linie numărul natural $N{~i~}$, semnificând dimensiunea celui de-al $i$-lea arbore. Pe următoarele $N{~i~}-1$ linii, se vor afla $N{~i~}-1$ perechi de numere $a$ şi $b$, semnificând că al $i$-lea arbore conţine muchia $(a, b)$.
h2. Date de ieşire
În fişierul de ieşire $grarbore.out$ ...
În fişierul de ieşire *grarbore.out* veţi afişa $T$ linii. Pe a i-a dintre acestea veţi afişa $N{~i~}-1$ valori, a $k$-a dintre acestea fiind egală cu numărul de subarbori ai celui de-al $i$-lea arbore pentru care gradul maxim al unui nod din subarbore este exact $k$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $T = 5$
* $1 ≤ N{~i~} ≤ 500.$
* Nodurile sunt numerotate de la $0$.
* Pentru $60%$ dintre teste $n ≤ 250$
* Pentru $10%$ dintre teste $n ≤ 10$
* Raspunsul trebuie afisat modulo $666013$
h2. Exemplu
table(example). |_. grarbore.in |_. grarbore.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
table(example). |_. grarbore.in |_. grarbore.out |_. Explicatie |
| 1
5
0 1
0 2
1 3
1 4
| 4 6 2 0
| Există 4 arbori pentru care gradul maxim al unui nod este 1, formaţi din submulţimile de noduri :
(0, 1), (0, 2), (1, 3), (1, 4).
Există 6 arbori pentru care gradul maxim al unui nod este 2, formaţi din submulţimile de noduri :
(0, 1, 2), (0, 1, 3), (0, 1, 4), (1, 3, 4),(0, 1, 2, 3), (0, 1, 2, 4).
Există 2 arbori pentru care gradul maxim al unui nod este 3, formaţi din submulţimile de noduri :
(0, 1, 3, 4), (0, 1, 2, 3, 4).
Nu există niciun arbore pentru care gradul maxim al unui nod este 4.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="grarbore") ==
