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

#include <bits/stdc++.h>


using namespace std;

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

vector <int> G[101];
int n  , p , x , y , k , T[102] , P[101] , C[101] , d[101];

int dfs(int x)
{
    P[x] = 1;
    d[x] = C[x];
    for(auto i:G[x])
        if(!P[i])
        {
            d[x] += dfs(i);
        }
    return d[x];
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> T[i];
        if(T[i] != 0)
            G[T[i]].push_back(i);
        if(T[i] == 0) p = i;
    }

    for(int i = 1 ; i <= n ; i++)
        cin >> C[i];

    d[p] = dfs(p);
    int maxi = -9999;
    for(int i = 1 ; i <= n ; i++)
        if(d[i] > maxi) maxi = d[i];

    for(int i = 1 ; i <= n ; i++)
        if(d[i] == maxi) cout << i << " ";
}