Submission #74771563

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using mint = modint1000000007;
#define nl '\n'
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for(ll i = 0; i < (ll)(n); ++i)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ull BigPrime = (1LL << 61) - 1;
const ll INF = (1LL << 60);
//--------------------------------------------------------------------------------
//--------------------------------------------------------------------------------


void solve()
{
    int n; cin >> n;
    vector<vector<int>> g(n);
    for(int i = 1; i < n; ++i)
    {
        int p; cin >> p;
        p--;
        g[p].push_back(i);
    }
    vector<ll> w(n);
    rep(i, n) cin >> w[i];

    vector<ll> dp = w;
    
    auto dfs = [&](auto dfs, int i, int par) -> void
    {
        for(int nex:g[i])
        {
            if(nex == par) continue;
            dfs(dfs, nex, i);
            dp[i] += dp[nex];
        }
    };

    dfs(dfs, 0, -1);

    ll ans = -INF;
    rep(i, n)
    {
        if(g[i].size() >= 2)
        {
            ll ma = -INF;
            ll mi = INF;

            for(int nex:g[i]) chmax(ma, dp[nex]), chmin(mi, dp[nex]);

            chmax(ans, ma - mi);
        }else
        {
            chmax(ans, 0LL);
        }
    }

    cout << ans << nl;
}

//--------------------------------------------------------------------------------

int main()
{
    //cout << fixed << setprecision(10); //Be careful!
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Submission Info

Judge Result