tairos
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.
Să se determine câte noduri se află la distanță D
de rădăcina arborelui infinit.
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]
.
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
.
2 ≤ N ≤ 100
1 ≤ D ≤ 10.000
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.1
;17
puncte avem N = 3
22
puncte răspunsul este ≤ 10 000
;tairos.in
4
3
1 2
3 1
3 4
tairos.out
5
tairos.in
5
3
1 2
3 1
3 5
4 3
tairos.out
8
tairos.in
5
25
2 1
2 3
1 4
5 2
tairos.out
33554432
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
ID: 22
Upload: liviu
Input: tairos.in/tairos.out
Memory limit: 64MB/32MB
Time limit: 0.2s
Author: Radu Muntean
Source: OJI 2019 XI-XII: Problema 3
Points by default: 10p