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

countsub.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema CountSub:

#include <iostream>
#include <fstream>
#define NN 1005
using namespace std;

ifstream fin("countsub.in");
ofstream fout("countsub.out");

int n, info[NN], st[NN], dr[NN];

void citire()
{
    fin >> n;
    for(int i =1 ; i <= n ; ++i)
        fin >> info[i] >> st[i] >> dr[i];
}

int radacina()
{
    int v[NN];
    for(int i =1 ; i <= n ; ++i)
        v[i] = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(st[i] != 0)
            v[st[i]] = 1;
        if(dr[i] != 0)
            v[dr[i]] = 1;
    }
    for(int i = 1 ; i <= n ; ++i)
        if(v[i] == 0)
            return i;
    return 0;
}

int count(int x)
{
    if (x)
        return 1 + count(st[x]) + count(dr[x]);
    else
        return 0;
}

int main()
{
    citire();
    int k , x;
    fin >> k;
    for(int i = 1 ; i <= k ; i ++)
    {
        fin >> x;
        fout << count(x)<< endl;
    }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #674 CountSub

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #674 CountSub de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #674 CountSub