Submission #2121839

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<bitset>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define EPS 1e-9
 
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

vector<int> children[20], cost(20, 0);
vector<int> x(20);

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    rep(n) cin >> x[i];
    reppp(i, 1, n){
        int tmp;
        cin >> tmp;
        children[tmp-1].push_back(i);
    }
    

    for(int i=n-1;i>=0;i--){
        if(children[i].empty()){
            cost[i] = x[i];
        }else{
            sort(all(children[i]), [&](int a, int b){
                return cost[a]-x[a] > cost[b]-x[b];
            });
            int tmp = 0, tmpans = 0;
            for(int c: children[i]){
                tmpans = max(tmpans, tmp+cost[c]);
                tmp += x[c];
            }
            cost[i] = max(tmpans, tmp+x[i]);
        }
    }

    cout << *max_element(all(cost)) << endl;
}

Submission Info

Judge Result