Cerința

Considerăm un arbore binar cu n noduri în care fiecare nod este numerotat de la 1 la n și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul 0, descendenții direcți ai rădăcinii pe nivelul 1, etc. Să se determine numărul de nivele k din arbore și, pentru fiecare nivel i de la 0 la k, numărul de noduri situate pe acel nivel.

Date de intrare

Fișierul de intrare nivelebin.in conține pe prima linie numărul n. Fiecare dintre următoarele n linii conține câte 3 numere X st dr; linia i + 1 din fișier conține informațiile despre nodul numerotat cu i: X reprezintă valoare din nod, st reprezintă numărul de ordine al descendentului stâng sau 0 dacă nodul i nu are descendent stâng, iar dr reprezintă numărul de ordine al descendentului drept sau 0 dacă nodul i nu are descendent drept.

Date de ieșire

Fișierul de ieșire nivelebin.out va conține pe prima linie numărul k, iar pe a doua linie k+1 numere naturale separate prin exact un spațiu, al i-lea număr reprezentând numărul de noduri situate pe nivelul i-1 din arbore.

Restricții și precizări

• 1 ≤ n ≤ 1000
• valorile din nodurile arborelui vor fi mai mici sau egale cu 1.000.000

Exemplu

nivelebin.in

6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0

nivelebin.out

3
1 2 3

Explicație

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

Arborele conține trei nivele:

• nivelul 0 conține doar rădăcina, nodul numerotat cu 4
• nivelul 1 conține două noduri, cele numerotate cu 1 2
• nivelul 2 conține trei noduri, cele numerotate cu 3 5 6

#include <bits/stdc++.h>
using namespace std;

ifstream cin("nivelebin.in");
ofstream cout("nivelebin.out");

int n , St[1001] , Dr[1001] , val[1001] , T[1001] , nivel[1001] , maxi , cnt;

void RSD(int p)
{
    if(p > 0)
    {
        cnt++;
        nivel[p] = cnt;
        RSD(St[p]);
        RSD(Dr[p]);
        cnt--;
    }
}

 int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> val[i] >> St[i] >> Dr[i];
        T[St[i]] = i;
        T[Dr[i]] = i;
    }
    int rez;
    for(int i = 1 ; i <= n ; i++)
        if(!T[i]) rez = i;
    RSD(rez);

    for(int i = 1 ; i <= n ; i++)
        if(nivel[i] > maxi) maxi = nivel[i];
      cout << maxi << endl;
    for(int i = 1 ; i <= maxi ; i++)
    {
        int cnt = 0;
        for(int j = 1 ; j <= n ; j++)
            if(nivel[j] == i) cnt++;
            cout << cnt << " ";
    }

}