== include(page="template/taskheader" task_id="grarbore") ==
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).
Poveste şi cerinţă...
h2. Date de intrare
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).
Fişierul de intrare $grarbore.in$ ...
h2. Date de ieşire
În fişierul de ieşire *grarbore.out* veţi afişa T linii. Pe a i-a dintre acestea veţi afişa Ni-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.
În fişierul de ieşire $grarbore.out$ ...
h2. Restricţii
* T = 5 1 ≤ Ni ≤ 500.
* Nodurile sunt numerotate de la 0.
* Pentru 60% dintre teste n ≤ 250
* Pentru 10% dintre teste n ≤ 10
* $... ≤ ... ≤ ...$
h2. Exemplu
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.
|
table(example). |_. grarbore.in |_. grarbore.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="grarbore") ==
