Tree game

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<ll> a(n+1, 0);
    for(int i=1;i<=n;i++) cin >> a[i];
    
    vector<vector<int>> children(n+1, vector<int>());
    for(int i=1;i<=n;i++){
        ll p;
        cin >> p;
        if(i !=1){
            children[p].push_back(i);
        }
    }
    
    vector<ll> f(n+1, 0);
    
    stack<pair<int, int>> stk;
    stk.emplace(1, 0);
    
    while(!stk.empty()){
        pair<int, int> current = stk.top();
        stk.pop();
        int u = current.first;
        int state = current.second;
        
        if(state ==0){
            stk.emplace(u,1);
            for(auto it = children[u].rbegin(); it != children[u].rend(); it++) {
                stk.emplace(*it,0);
            }
        }
        else{
            if(children[u].empty()){
                f[u] = a[u];
            }
            else{
                ll max1 = -1;
                int cnt1 =0;
                ll max2 = -1;
                for(auto &v: children[u]){
                    if(f[v] > max1){
                        max2 = max1;
                        max1 = f[v];
                        cnt1 =1;
                    }
                    else if(f[v] == max1){
                        cnt1 +=1;
                    }
                    else{
                        if(f[v] > max2){
                            max2 = f[v];
                        }
                    }
                }
                if(cnt1 >=2){
                    f[u] = a[u] + max1;
                }
                else{
                    if(children[u].size() >=2){
                        f[u] = a[u] + max2;
                    }
                    else{
                        f[u] = a[u];
                    }
                }
            }
        }
    }
    
    cout << f[1];
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED