Submission #74772052

---

Source Code Expand

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

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

    int N;
    cin >> N;

    vector<int> parent(N + 1, 0);
    vector<vector<int>> children(N + 1);

    for (int i = 2; i <= N; i++) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }

    vector<ll> W(N + 1), S(N + 1);
    for (int i = 1; i <= N; i++) cin >> W[i];
    vector<int> order;
    order.reserve(N);
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int c : children[u]) q.push(c);
    }

    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        S[u] = W[u];
        for (int c : children[u]) S[u] += S[c];
    }

    ll ans = 0;
    for (int u = 1; u <= N; u++) {
        if (children[u].size() < 2) continue;
        ll mx = LLONG_MIN, mn = LLONG_MAX;
        for (int c : children[u]) {
            mx = max(mx, S[c]);
            mn = min(mn, S[c]);
        }
        ans = max(ans, mx - mn);
    }

    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result