Overview

This problem asks us to find the maximum imbalance degree among all managers in an organization represented as a tree structure, where the imbalance degree is defined as the difference between the maximum and minimum workloads of a manager’s direct subordinates’ teams.

Observations

The organization is represented as a rooted tree, with employee 1 as the root (president). Key observations are: - Only regular employees (leaf nodes) have actual workloads, while managers (internal nodes) have a workload of 0 - The imbalance degree of an employee is defined as the difference between the maximum and minimum workloads among the teams led by their direct subordinates - If an employee has 1 or fewer subordinates, the imbalance degree is 0

A naive approach that recomputes subtree workloads for each node would result in a time complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\). To compute this efficiently, a bottom-up (leaf to root) approach is needed.

Algorithm

1. Tree construction: Build an adjacency list from the input
2. Determining DFS order: Use a stack to determine the depth-first search order (post-order traversal)
3. Bottom-up computation:
   • Leaf nodes: Set the node’s workload as its subtree workload
   • Internal nodes: Compute the sum of all children’s subtree workloads
   • If the node has 2 or more subordinates, compute the difference between the maximum and minimum workloads of the subordinate teams, and update the answer

This approach is efficient because each node is processed exactly once.

Complexity

• Time complexity: \(O(N)\) — each node is processed exactly once
• Space complexity: \(O(N)\) — linear memory is used for the graph representation and working arrays

Implementation Details

• Use iterative DFS with a stack to avoid recursion depth limits

• Store the post-order traversal in a list and then process it in reverse order

• Aggregate the workloads of child nodes while simultaneously computing the imbalance degree

• Skip nodes with 1 or fewer subordinates to save computation cost

  Source Code

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    P_list = list(map(int, data[1:1+n-1]))
    W_list = list(map(int, data[1+n-1:1+n-1+n]))
    
    graph = [[] for _ in range(n+1)]
    for i in range(2, n+1):
        p = P_list[i-2]
        graph[p].append(i)
    
    total_work = [0] * (n+1)
    ans = 0
    
    stack = [1]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph[u]:
            stack.append(v)
    
    for u in reversed(order):
        if not graph[u]:
            total_work[u] = W_list[u-1]
        else:
            child_works = []
            for v in graph[u]:
                total_work[u] += total_work[v]
                child_works.append(total_work[v])
            
            if len(child_works) >= 2:
                max_val = max(child_works)
                min_val = min(child_works)
                ans = max(ans, max_val - min_val)
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.