Rezolvare PBinfo #651

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