# PBinfo #2971 – tairos – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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 trei 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ă două etape de prelungire a frunzelor.



Cerința
Să se determine câte noduri se află la distanță D de rădăcina arborelui infinit.

Date de intrare
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 două numere întregi x și y cu semnificația că în arborele dat inițial există muchia [x, y].

Date de ieșire
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.

Restricții și precizări

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;
În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:
tairos.in

4
3
1 2
3 1
3 4
tairos.out

5
Explicație
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.

Exemplul 2:
tairos.in

5
3
1 2
3 1
3 5
4 3
tairos.out

8
Exemplul 3:
tairos.in

5
25
2 1
2 3
1 4
5 2
tairos.out

33554432

## Cod sursă C++

```cpp
/// autor Ciobanu Bogdan
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <memory>
using namespace std;
const int MAX_N = 100, MAX_D = 10000;
const int MOD = int(1e9) + 7;
bool A[MAX_N][MAX_N];
int p[MAX_N], d[MAX_N];
int dp[2][MAX_D + 1];
int N;
bool is_leaf(int node) {
	if (node == 0) return false;
	bool has_adj = false;
	for (int i = 0; i < N; ++i) if (A[node][i]) {
		if (has_adj) return false;
		has_adj = true;
	}
	return true;
}
int main() {
	unique_ptr<FILE, decltype(&fclose)> f(fopen("tairos.in", "r"), fclose);
	int D; fscanf(f.get(), "%d%d", &N, &D);
	for (int _ = 0; _ < N - 1; ++_) {
		int x, y; fscanf(f.get(), "%d%d", &x, &y); --x; --y;
		A[x][y] = A[y][x] = true;
	}
	fill(p + 1, p + N, -1);
	while (true) {
		bool changed = false;
		for (int i = 0; i < N; ++i) if (p[i] != -1) {
			for (int j = 0; j < N; ++j) if (A[i][j] && p[j] == -1) {
				p[j] = i;
				d[j] = d[i] + 1;
				changed = true;
			}
		}
		if (!changed) break;
	}
	dp[0][0] = 1;
	for (int s = 0; s <= D; ++s) {
		for (int i = 0; i < N; ++i) if (s + d[i] <= D) {
			(dp[!is_leaf(i)][s + d[i]] += dp[0][s]) %= MOD;
		}
	}
	f.reset(fopen("tairos.out", "w"));
	fprintf(f.get(), "%d\n", dp[1][D]);
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2971)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2971/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2971/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)