Overview

In an organization represented as a rooted tree, for each employee we compute the difference between the maximum and minimum workload (subtree sum) among the teams led by their direct subordinates, and output the maximum of this value across all employees.

Analysis

Key Observations

1. Only leaf nodes have workload: Since employees with subordinates (internal nodes) have \(W_i = 0\), the total workload of the subtree rooted at some employee \(u\) equals the sum of \(W_i\) over all leaf nodes contained in that subtree.

2. Definition of imbalance: The imbalance of employee \(v\) is computed by calculating the “total subtree workload \(S(c_j)\)” for each of \(v\)’s direct subordinates \(c_1, c_2, \ldots, c_k\), and taking the difference \(\max(S(c_j)) - \min(S(c_j))\). If there is at most one direct subordinate, the difference cannot be taken, so it is \(0\).

3. What needs to be done: Once we compute the total subtree workload for each node, we simply take the difference between the maximum and minimum subtree sums among each node’s children.

Is a Naive Approach Sufficient?

The subtree sum for each node can be computed in \(O(N)\) by accumulating from leaves toward the root. Then, for each node, finding the maximum and minimum subtree sums among its children also takes \(O(N)\) in total, since the total number of children across all nodes is \(N-1\). Therefore, the entire problem can be solved in \(O(N)\), which is sufficiently fast for \(N \leq 2 \times 10^5\).

Algorithm

1. Build the tree: From the input, construct a children list children for each node.
2. Compute subtree workload sums:
   • Use an iterative DFS with a stack to obtain a topological order (from root to leaves).
   • Process in reverse order (from leaves to root): for a leaf, \(S(\text{node}) = W[\text{node}]\); for an internal node, \(S(\text{node}) = \sum_{c \in \text{children}(\text{node})} S(c)\).
3. Compute imbalance:
   • For each node \(v\), if it has two or more children, compute the difference between the maximum and minimum of the children’s subtree sums \(S(c)\).
   • The answer is the maximum of this difference across all nodes.

Concrete Example

For example, suppose employee 1 is the president with subordinates employee 2 and employee 3, employee 2 has subordinates employee 4 and employee 5 (both leaves), and employee 3 is a leaf. With \(W = [0, 0, 5, 3, 7]\):

• \(S(4) = 3, S(5) = 7, S(3) = 5\)
• \(S(2) = 3 + 7 = 10\)
• Imbalance of employee 2: \(7 - 3 = 4\)
• Imbalance of employee 1: \(\max(10, 5) - \min(10, 5) = 5\)
• Answer: \(\max(4, 5) = 5\)

Complexity

• Time complexity: \(O(N)\) (tree construction, subtree sum computation, and imbalance computation are all linear)
• Space complexity: \(O(N)\) (tree adjacency list, subtree sum array, DFS stack, etc.)

Implementation Notes

• Iterative DFS instead of recursion: Since \(N\) can be up to \(2 \times 10^5\), Python’s recursion limit (default 1000) may be exceeded. By using an iterative DFS with a stack to obtain topological order and processing in reverse, we avoid recursion.

• Fast input reading: By reading all input at once with sys.stdin.buffer.read() and splitting into tokens with split(), we can handle large inputs efficiently.

• Special case \(N = 1\): When there is only one employee, no subordinates exist, so the imbalance is \(0\). Since the parent input line would be empty, we handle this case first.

  Source Code

import sys
from sys import setrecursionlimit

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    if N == 1:
        print(0)
        return
    
    children = [[] for _ in range(N + 1)]
    for i in range(2, N + 1):
        p = int(input_data[idx]); idx += 1
        children[p].append(i)
    
    W = [0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = int(input_data[idx]); idx += 1
    
    # Compute subtree sums iteratively
    subtree_sum = [0] * (N + 1)
    
    # Topological order via iterative DFS
    order = []
    stack = [1]
    while stack:
        node = stack.pop()
        order.append(node)
        for c in children[node]:
            stack.append(c)
    
    # Process in reverse order (leaves first)
    for node in reversed(order):
        if not children[node]:
            subtree_sum[node] = W[node]
        else:
            s = 0
            for c in children[node]:
                s += subtree_sum[c]
            subtree_sum[node] = s
    
    # Compute answer
    ans = 0
    for v in range(1, N + 1):
        if len(children[v]) >= 2:
            child_sums = [subtree_sum[c] for c in children[v]]
            max_val = max(child_sums)
            min_val = min(child_sums)
            diff = max_val - min_val
            if diff > ans:
                ans = diff
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.