Cerința

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile p din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în p este maximă.

Date de intrare

Fișierul de intrare sumsubmax.in conține pe prima linie numărul de noduri n. Pe a doua linie se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe linia a treia se află, în ordine, valorile asociate nodurilor din arbore, separate și ele prin spații.

Date de ieșire

Fișierul de ieșire sumsubmax.out va conține, în ordine crescătoare, nodurile p din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în p este maximă, separate printr-un spațiu.

Restricții și precizări

1 ≤ n ≤ 100
în vectorul de tați rădăcina este marcată cu 0
valorile asociate nodurilor din arbore sunt numere întregi din intervalul [-1000,1000]

Exemplu

sumsubmax.in

8
4 3 0 3 2 1 2 1
-3 2 -7 4 0 3 3 1

sumsubmax.out

2 4

Explicație

În subarborii cu rădăcina în 2 și 4 suma valorilor asociate nodurilor este 5 și este maximă.

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 SumSubMax:

#include <iostream>
#include <fstream>
using namespace std;

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

int n , t[105], v[105] , sum[105];

void  dfs(int k)
{
    int s = 0;
    for(int i = 1 ; i <= n ; ++i)
        if(t[i] == k)
        {
            dfs(i);
            s += sum[i];
        }
    sum[k] = s + v[k];
}

int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; i ++)
        fin >> t[i];
    for(int i = 1 ; i <= n ; i ++)
        fin >> v[i];
    int r = 0 ;
    for(int i = 1 ; i <= n ; i ++)
        if(t[i] == 0)
            r = i;
    dfs(r);
    int smax = sum[1];
    for(int i = 1 ; i <= n ; ++i)
        if(smax < sum[i])
            smax = sum[i];
    for(int i = 1 ; i <= n ; ++i)
        if(smax == sum[i])
            fout << i << " ";
    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 #651 SumSubMax

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #651 SumSubMax 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 #651 SumSubMax