== include(page="template/taskheader" task_id="tairos") ==
Poveste şi cerinţă...
Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$.
Arborele se va transforma astfel: la oricare etapă fiecare nod de gradul $1$ diferit de rădăcină din arborele
actual se înlocuieşte cu un arbore identic cu cel dat iniţial, iar la următoarea etapă procedeul se va relua
pentru arborele obţinut, formându-se astfel un arbore infinit. În următoarele $3$ imagini se prezintă un
exemplu de arbore dat iniţial, arborele obţinut după prima etapă de prelungire a frunzelor şi arborele
obţinut după $2$ etape de prelungire a frunzelor.
!problema/tairos?Untitled2.jpg!
Să se determine câte noduri se află la distanţă $D$ de rădăcina arborelui infinit.
h2. Date de intrare
Fişierul de intrare $tairos.in$ ...
Pe prima linie a fişierului de intrare tairos.in se va afla un număr natural $N$, reprezentând numărul de
noduri din arborele dat iniţial. Pe a doua linie se va afla numărul întreg $D$, cu semnificaţia de mai sus, iar
fiecare dintre următoarele $N-1$ linii conţine câte $2$ numere întregi $x$ şi $y$ cu semnificaţia că în arborele dat
iniţíal există muchia $[x,y]$.
h2. Date de ieşire
În fişierul de ieşire $tairos.out$ ...
Fişierul de ieşire tairos.out va conţine un singur număr, şi anume restul împărţirii numărului de
noduri cerut la numărul $1.000.000.007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100$
* $1 ≤ D ≤ 10.000$
* Un arbore este un graf neorientat, conex şi fără cicluri.
* Distanţa dintre două noduri $x$ şi $y$ ale unui arbore este egală cu numărul de muchii ale unui lanţ
cu extremităţile în nodurile $x$ şi $y$, lanţ format din noduri distincte.
* Rădăcina va fi considerată ca fiind nodul 1;
* Pentru teste în valoare de $17$ puncte avem $N = 3$
* Pentru teste în valoare de alte $22$ puncte răspunsul este $≤ 10 000$;
h2. Exemplu
table(example). |_. tairos.in |_. tairos.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
3
1 2
3 1
3 4
| 5
|
| 5
3
1 2
3 1
3 5
4 3
| 8
|
| 5
25
2 1
2 3
1 4
5 2
| 33554432
|
h3. Explicaţie
...
Pentru primul test, arborele dat în fişierul de intrare are 4 noduri. Se cere numărul
nodurilor aflate la distanţa 3 faţă de rădăcină.
Urmărind imaginile din exemplele de mai sus,la distanţa 3 avem
următoarele 5 noduri: 222, 223, 241, 421 şi 43
== include(page="template/taskfooter" task_id="tairos") ==
