Overview

This problem involves an organizational chart represented as a rooted tree. For each employee, we need to find the difference between the maximum and minimum “workload of teams led by their direct subordinates (sum of weights of subtrees),” and then find the maximum of this value across all employees.

Analysis

To solve this problem, we need to know the following two pieces of information for each employee: 1. Team workload: The total sum of workloads \(W_i\) of all employees contained in the subtree rooted at that employee. 2. Maximum and minimum team workloads among direct subordinates: Needed to calculate the degree of imbalance.

Leveraging an Important Constraint

The constraint \(P_i \leq i - 1\) in the problem statement is extremely important. This means “a supervisor’s number is always smaller than their subordinate’s number,” indicating that the employee numbering forms a kind of topological order (from root to leaves).

By utilizing this property, we can perform bottom-up aggregation (from leaves to root) simply by processing employees in decreasing order of their number (from \(N\) down to \(2\)), without needing expensive graph traversals (DFS or BFS). This is because when processing employee \(i\), all aggregations for their subordinates (employees with numbers greater than \(i\)) are guaranteed to be already completed.

Naive Approach

If we were to traverse the subtree for each employee every time to compute the sum, the worst case would take \(O(N^2)\) time, which would not be fast enough for \(N = 2 \times 10^5\). Therefore, we need to accumulate computation results from lower levels upward, similar to dynamic programming (DP).

Algorithm

We find the solution using the following steps:

1. Initialization:

   • Initialize each employee’s team workload \(S_i\) with their own workload \(W_i\).
   • Prepare arrays to manage each employee’s “maximum subordinate workload child_max,” “minimum subordinate workload child_min,” and “number of subordinates child_count.”

2. Bottom-up aggregation:

   • Loop through employee numbers \(i\) from \(N\) down to \(2\) in reverse order.
   • Add employee \(i\)’s current team workload \(S_i\) to their supervisor \(P_i\)’s team workload \(S_{P_i}\).
   • Simultaneously, update supervisor \(P_i\)’s child_max, child_min, and child_count using \(S_i\).

3. Calculating the degree of imbalance:

   • Among all employees with child_count of 2 or more, find the maximum value of child_max - child_min.

Complexity

• Time complexity: \(O(N)\)
  • Reading input takes \(O(N)\), the bottom-up aggregation loop takes \(O(N)\), and the final maximum search takes \(O(N)\), so the overall algorithm runs in linear time.
• Space complexity: \(O(N)\)
  • Several arrays of length \(N\) are used to store each employee’s workload and supervisor information.

Implementation Notes

• Efficient input: When handling input of scale \(N=2 \times 10^5\) in Python, reading all input at once with sys.stdin.read().split() is faster than repeatedly calling input().

• 1-indexed vs 0-indexed: The problem uses employee numbers starting from 1, but within the program, adjustments need to be made to match array indices (starting from 0) (e.g., subtracting 1 from supervisor \(P_i\)).

• Initial value settings: The initial value of child_min should be set to a very large value, or it should be directly assigned when processing the first subordinate. In this code, -1 is used as a flag to determine whether it is the first subordinate.

  Source Code

import sys

def solve():
    # Read all input at once and split by whitespace to handle large input efficiently.
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    N = int(input_data[0])
    if N < 2:
        # If there's only one employee, they have no subordinates.
        # The unbalance degree of any employee with 1 or fewer subordinates is 0.
        print(0)
        return
        
    # P_2, P_3, ..., P_N are the direct supervisors of employees 2, 3, ..., N.
    # The input provides these N-1 values starting from the second element.
    # P[0] corresponds to P_2, P[1] to P_3, and so on.
    P = list(map(int, input_data[1:N]))
    
    # W_1, W_2, ..., W_N are the workloads assigned to each employee.
    # These N values start from index N in the input_data list.
    W = list(map(int, input_data[N:2*N]))
    
    # S[i] will store the total team workload (subtree sum) of employee i+1.
    # Initially, it is just the workload of the employee themselves.
    S = W
    
    # We need to track the maximum and minimum team workloads among the direct
    # subordinates of each employee to calculate their "unbalance degree".
    child_max = [-1] * N
    child_min = [-1] * N
    child_count = [0] * N
    
    # The problem guarantees that for each employee i (2 <= i <= N), P_i < i.
    # This property allows us to process the tree bottom-up by iterating from
    # N down to 2. When we process employee i, we can be certain that their
    # team workload S[i-1] has already incorporated all workloads from their
    # own subordinates (who must have indices greater than i).
    for i in range(N, 1, -1):
        # p_idx is the 0-indexed ID of the supervisor of employee i.
        # Since P[0] is the supervisor of employee 2, P[i-2] is the supervisor of employee i.
        p_idx = P[i-2] - 1
        
        # s_val is the total team workload of employee i.
        s_val = S[i-1]
        
        # Add employee i's team workload to their supervisor's total team workload.
        S[p_idx] += s_val
        
        # Update the supervisor's records regarding their direct subordinates.
        child_count[p_idx] += 1
        if child_max[p_idx] == -1:
            # This is the first child processed for this supervisor.
            child_max[p_idx] = s_val
            child_min[p_idx] = s_val
        else:
            # Compare this child's team workload with current max and min.
            if s_val > child_max[p_idx]:
                child_max[p_idx] = s_val
            if s_val < child_min[p_idx]:
                child_min[p_idx] = s_val
                
    # The organization's unbalance degree is the maximum unbalance degree among all employees.
    max_unbalance = 0
    for i in range(N):
        # An employee's unbalance degree is only non-zero if they have at least 2 children.
        if child_count[i] >= 2:
            unbalance = child_max[i] - child_min[i]
            if unbalance > max_unbalance:
                max_unbalance = unbalance
                
    # Output the final result.
    sys.stdout.write(str(max_unbalance) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.