# PBinfo #651 – SumSubMax – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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ă.

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/651)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/651/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-651/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)