A company has n employees numbered 0 to n-1. Each employee has exactly one direct manager given in manager[i], except the head of the company (manager[headID] == -1). An employee needs informTime[i] minutes to inform all their direct subordinates. Return the total time needed to inform all employees.

Examples

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: Only the head, no one to inform.

Example 2:

Input: n = 6, headID = 2,
       manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: Head (2) informs all 5 subordinates in 1 minute.

Example 3:

Input: n = 7, headID = 6,
       manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: Chain 6→5→4→3→2→1→0, total = 1+2+3+4+5+6 = 21.

Constraints

  • 1 <= n <= 10^5
  • 0 <= headID < n
  • manager.length == n
  • informTime.length == n
  • informTime[i] >= 0
  • The input forms a valid tree

Thinking Process

Baseline (Naive) – O(n^2)

For each employee, walk up through manager[i] → manager[manager[i]] → ... → head and sum informTime along the path. Track the maximum. In a chain structure each walk is O(n), giving O(n^2) total.

Bottleneck

Repeated traversal of the same paths – computing the same prefix sums over and over.

Optimization

This is a tree rooted at headID where manager → subordinate forms a directed edge. The problem becomes:

Find the longest weighted path from root to any leaf.

Build an adjacency list and traverse once with DFS or BFS. Each node is visited exactly once.

DFS Recurrence

$text{time}(node) = text{informTime}[node] + max_{child}(text{time}(child))

Base case: leaf nodes have no children, so max(child times) = 0.

Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Baseline (Naive) – O(n^2)$

Walkthrough — input n = 1, headID = 0, manager = [-1], informTime = [0], expected output 0:

Only the head, no one to inform.

Common Mistakes

  • Confusing the direction: edges go from manager to subordinates, not the other way
  • Adding informTime of leaf nodes (leaves have informTime = 0 but the logic should still be correct since it adds 0)
  • Forgetting to propagate accumulated time in BFS (each child’s time = parent’s accumulated time + parent’s informTime)

Key Takeaways

  • “Maximum time from root to any leaf” = longest path in a weighted tree = single DFS/BFS
  • Building an adjacency list from the manager[] array converts the problem into standard tree traversal
  • DFS gives a clean recursive formulation; BFS carries accumulated time as state in the queue

References

Template Reference