Fişierul intrare/ieşire:grarbore.in, grarbore.outSursăLot Râmnicu Vâlcea 2015 - Baraj 3 Seniori
AutorEugenie Daniel Posdarascu, Vlad GavrilaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test3.3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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).

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 Ni, semnificând dimensiunea celui de-al i-lea arbore. Pe următoarele Ni-1 linii, se vor afla Ni-1 perechi de numere a şi b, semnificând că al i-lea arbore conţine muchia (a, b).

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.

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
  • Raspunsul trebuie afisat modulo 666013

Exemplu

grarbore.ingrarbore.outExplicatie
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?