Overview

For each employee (vertex), we need to compute “max − min of the subtree workloads among their direct subordinates,” and then find the maximum of this value across the entire organization (the overall imbalance). The key point is efficiently computing the subtree workload (subtree sum) for all vertices.

Analysis

Key Observations

• “The workload of the team led by employee \(u\)” is the total sum of the subtree rooted at \(u\) (subtree sum).
• The imbalance of employee \(v\) is obtained by collecting the subtree sums of each of \(v\)’s direct subordinates and taking
  \(\max - \min\) (if \(v\) has \(0\) or \(1\) subordinates, the imbalance is \(0\)).

Therefore, what we need is: 1. The subtree sum \(sub[i]\) for each vertex \(i\) 2. For each vertex \(v\), the minimum and maximum of \(sub[\text{child}]\) among its children (direct subordinates)

Why a Naive Approach Is Too Slow

• If we run a DFS for each vertex to compute “its children’s subtree sums,” the worst case is \(O(N^2)\).
• If we run a single DFS over the entire tree to compute subtree sums and then take the max/min among children at each vertex, it would be \(O(N)\). However, in Python, recursive DFS can reach a depth of up to \(2\times 10^5\), which easily causes recursion limit and stack issues.

How to Solve This

In this problem, the input constraint \(P_i \le i-1\) guarantees that a parent’s index is always smaller than its child’s index.
This means vertices with larger indices are closer to the leaves, so by processing in reverse order i = N, N-1, ..., 1, we can naturally aggregate subtree sums from children to parents (no recursion needed).

Algorithm

We manage the following arrays and process vertices in reverse order from \(N\) to \(1\).

• sub[i]: subtree sum of vertex \(i\) (initialized to \(W_i\))
• minc[i]: minimum subtree sum among vertex \(i\)’s children
• maxc[i]: maximum subtree sum among vertex \(i\)’s children
• cnt[i]: number of children of vertex \(i\) (number of direct subordinates)

Processing steps (scanning i in reverse order): 1. If cnt[i] >= 2, the imbalance of vertex \(i\) is maxc[i] - minc[i]. Update the answer ans. 2. When \(i \ge 2\), for parent \(p = P_i\): - sub[p] += sub[i] (add subtree sum to parent) - minc[p] = min(minc[p], sub[i]) - maxc[p] = max(maxc[p], sub[i]) - cnt[p] += 1

This way, each child’s subtree sum is reflected to its parent exactly once, and the maximum imbalance across all vertices is obtained.

Example: If vertex \(v\) has children \(a, b, c\) with subtree sums \(10, 25, 18\), then
the imbalance is \(25 - 10 = 15\). We output this as the maximum across all vertices.

Complexity

• Time complexity: \(O(N)\) (each vertex is processed once, and the update to its parent is also done once)
• Space complexity: \(O(N)\) (arrays such as sub, minc, maxc, cnt, parent)

Implementation Notes

• Initialize minc with a sufficiently large value (e.g., INF = 10**30) and maxc with a sufficiently small value to simplify updates.

• Since the imbalance is \(0\) when a vertex has \(1\) or fewer subordinates, we only compute the difference when cnt[i] >= 2.

• Since the input can be large, reading all at once with sys.stdin.buffer.read() is faster.

• The essence of this solution is avoiding recursion and aggregating in reverse order by exploiting the property \(P_i < i\).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N = data[idx]
    idx += 1

    parent = [0] * (N + 1)
    for i in range(2, N + 1):
        parent[i] = data[idx]
        idx += 1

    w = [0] * (N + 1)
    for i in range(1, N + 1):
        w[i] = data[idx]
        idx += 1

    INF = 10**30
    sub = w[:]  # subtree sums
    minc = [INF] * (N + 1)
    maxc = [-INF] * (N + 1)
    cnt = [0] * (N + 1)

    ans = 0
    for i in range(N, 0, -1):
        if cnt[i] >= 2:
            diff = maxc[i] - minc[i]
            if diff > ans:
                ans = diff
        if i >= 2:
            p = parent[i]
            si = sub[i]
            sub[p] += si
            if si < minc[p]:
                minc[p] = si
            if si > maxc[p]:
                maxc[p] = si
            cnt[p] += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.