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. Se dau k noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod.

Date de intrare

Fișierul de intrare countsub.in conține pe prima linie numărul n. Fiecare dintre următoarele n linii contine câte 3 numere X st dr; linia i + 1 din fișier conține informatiile 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.

Pe următoarea linie se află numărul k, iar pe fiecare dintre următoarele k linii se află câte un număr natural cuprins între 1 și n, reprezentând nodul curent.

Date de ieșire

Fișierul de ieșire countsub.out va conține k linii; fiecare linie va conține numărul de noduri din subarborele cu rădăcina în nodul corespunzător.

Restricții și precizări

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

Exemplu

countsub.in

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

countsub.out

3
2
6
2

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.

#include <bits/stdc++.h>

using namespace std;

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

int n , St[1001] , Dr[1001] , val[1001] , T[1001] , k , x , cnt;

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

 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;
    }

    cin >> k;
    for(int i = 1 ; i <= k ; i++)
    {
        cin >> x;
        cnt = 0;
        RSD(x);
        cout << cnt << '\n';
    }

}