grarbore

Grarbore

== 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") ==