Submission #74771400

---

Source Code Expand

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

#define int long long
const int inf = 1e18;

void solve(){

    int n; cin >> n;

    vector<vector<int>> graph(n + 1);

    for(int i = 2; i <= n; i++){
        int u; cin >> u;
        graph[u].push_back(i);
        graph[i].push_back(u);
    }
    vector<int> a(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    vector<int> w(n + 1, 0);
    auto dfs = [&](int u, int par, auto && self) -> void {
        
        int sum = a[u];

        for(auto &v: graph[u]){
            if(v == par) continue;

            self(v, u, self);

            sum += w[v];
        }

        w[u] = sum;
    };

    dfs(1, 0, dfs);

    int ans = 0;

    auto dfs2 = [&](int u, int par, auto && self) -> void {
        int mx = -1, mn = inf;

        for(auto &v: graph[u]){

            if(par == v) continue;
            mx = max(mx, w[v]);
            mn = min(mn, w[v]);

            self(v, u, self);
        }

        if(mx != 0){
            ans = max(ans, mx - mn);
        }
        
    };

    dfs2(1, 0, dfs2);

    cout << ans << endl;


}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc = 1;
    // cin >> tc;
    while (tc--) solve();
}

Submission Info

Judge Result