Problema Tairos – OJI 2019, Clasa a 11-a

Problema Tairos – OJI 2019, Clasa a 11-a

Rezumat

Se dă un arbore cu nn noduri și cu rădăcina în nodul 11 Acesta va fi modificat în mai multe etape. În fiecare etapă, se ia fiecare frunză din arborele curent și se înlocuiește cu o copie a arborelui inițial. Procedeul se repetă la infinit. Să se determine câte noduri din arborele infinit se află la distanța dd de rădăcină. Rezultatul va fi calculat modulo 109+710^9 + 7

Exemplu tairos

Soluție

Dacă numerotăm nivelurile arborelui infinit de la 00 atunci trebuie să determinăm numărul de noduri de pe nivelul dd În primul rând, sper să nu vă sperie faptul că arborele este infinit. Îl putem considera doar suficient de mare încât să nu mai putem crea noduri pe nivelul dd

Orice nod de pe nivelul dd trebuie să fie un nod non-frunză de pe nivelul xx al unei copii a arborelui inițial care a înlocuit la un moment dat o frunză de pe nivelul dxd - x Recitiți cu mare atenție această propoziție, pentru că aici stă cheia problemei. Să dau și un exemplu totuși:

Exemple niveluri

Aici nodul xx se află pe nivelul 33 din arborele infinit, și totodată pe nivelul 11 din arborele portocaliu cu rădăcina în tt aflat pe nivelul 31=23 - 1 = 2 Cât despre nodul yy putem fi tentați să afirmăm că se află pe nivelul 22 al arborelui cu rădăcina în tt dar de fapt se află pe nivelul 00 al arborelui roșu cu rădăcina în yy De asta mai sus am folosit termenul non-frunză. Când un nod pare a fi frunză într-un subarbore identic cu cel original, el este de fapt rădăcina copiei lipite în etapa următoare pe acea frunză.

Așadar, dacă notăm cu dp[i] numărul de noduri de pe nivelul ii care la un moment dat au fost frunze în arborele infinit, iar cu nonLeaves[i] numărul de noduri non-frunză de pe nivelul ii din arborele dat, atunci răspunsul problemei s-ar calcula așa:

int ans = 0;
for (int j = 0; j <= min(n - 1, d); j++)
ans += dp[d - j] * nonLeaves[j];

Mai avem de calculat vectorul dp. Pentru asta vom folosi programare dinamică, iar recurența este destul de simplă. Dacă la etapa curentă un nod de pe nivelul ii este frunză, atunci la etapa următoare acesta va contribui cu câte leaves[x] frunze pe fiecare nivel i+xi + x Prin leaves[i] am notat numărul de frunze de pe nivelul ii din arborele inițial. Dacă nivelul ii nu există, leaves[i] este considerat 00 Recurența este:

dp[i]={j=0min(n1,i)dp[ij]leaves[j]pentru i11pentru i=0\mathrm{dp}[i] = \begin{cases} \sum_{j = 0}^{\min(n - 1, i)} \mathrm{dp}[i - j] \cdot \mathrm{leaves}[j] & \text{pentru } i \ge 1\\ 1 & \text{pentru } i = 0 \end{cases}

Sursă C++

Mai întâi am făcut un DFS pe arborele inițial, calculând pe parcurs vectorii leaves și nonLeaves. Apoi am calculat dinamica și la final răspunsul problemei.

Problema Tairos
#include <bits/stdc++.h>
using namespace std;
ifstream fin("tairos.in");
ofstream fout("tairos.out");
const int MOD = 1e9 + 7;
int main() {
int n, d; fin >> n >> d;
vector<vector<int>> ad(n + 1);
for (int i = 1; i < n; i++) {
int x, y; fin >> x >> y;
ad[x].push_back(y);
ad[y].push_back(x);
}
vector<int> leaves(n + 1);
vector<int> nonLeaves(n + 1);
function<void(int, int, int)> dfs = [&](int node, int fath, int dpth) {
if (ad[node].size() == 1 && ad[node][0] == fath)
leaves[dpth]++;
else
nonLeaves[dpth]++;
for (int nghb : ad[node])
if (nghb != fath)
dfs(nghb, node, dpth + 1);
};
dfs(1, 0, 0);
vector<int> dp(d + 1);
dp[0] = 1;
for (int i = 1; i <= d; i++)
for (int j = 0; j <= min(n - 1, i); j++)
dp[i] = (dp[i] + 1LL * dp[i - j] * leaves[j]) % MOD;
int ans = 0;
for (int j = 0; j <= min(n - 1, d); j++)
ans = (ans + 1LL * dp[d - j] * nonLeaves[j]) % MOD;
fout << ans << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Tairos, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii