Submission #74771806

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 200005;
vector<int> adj[MAXN];
ll W[MAXN];
ll team_workload[MAXN];
ll max_global_imbalance = 0;

// Post-order traversal to calculate workloads and imbalance
void dfs(int u) {
    if (adj[u].empty()) {
        team_workload[u] = W[u];
        return;
    }

    ll total_sum = 0;
    ll max_s = -1;
    ll min_s = -1;

    for (int v : adj[u]) {
        dfs(v);
        ll s_v = team_workload[v];
        total_sum += s_v;

        if (max_s == -1 || s_v > max_s) max_s = s_v;
        if (min_s == -1 || s_v < min_s) min_s = s_v;
    }

    team_workload[u] = total_sum;

    // Only calculate imbalance if there are 2 or more subordinates
    if (adj[u].size() >= 2) {
        max_global_imbalance = max(max_global_imbalance, max_s - min_s);
    }
}

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

    int N;
    if (!(cin >> N)) return 0;

    // Building the tree
    for (int i = 2; i <= N; ++i) {
        int p;
        cin >> p;
        adj[p].push_back(i);
    }

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

    dfs(1);

    cout << max_global_imbalance << endl;

    return 0;
}

Submission Info

Judge Result