A company has n employees labeled from 0 to n - 1, and employee headID is the head. The head knows some news at time 0. Every other employee has one direct manager given by manager[i]; the head has manager -1. These relationships form a tree.
Once employee i receives the news, all of their direct reports receive it after informTime[i] minutes. Different employees can spread the news at the same time. Return the time when every employee knows the news.
Employees with no direct reports have an inform time of 0. The arrays are indexed by employee ID, and the head can have any ID.
Each edge is labeled with the time its manager takes to inform a direct report.
Example 1:
Input: n = 5
headID = 0
manager = [-1,0,0,1,1]
informTime = [2,3,0,0,0]
Output: 5Explanation: Employee 0 informs employees 1 and 2 after 2 minutes. Employee 1 then takes 3 more minutes to inform employees 3 and 4. Everyone knows the news after 5 minutes.
Example 2:
Input: n = 4
headID = 2
manager = [2,0,-1,2]
informTime = [4,0,1,0]
Output: 5Explanation: Head 2 informs employees 0 and 3 after 1 minute. Employee 0 then informs employee 1 after 4 more minutes, so the total is 5 minutes.
Example 3:
Input: n = 3
headID = 1
manager = [1,-1,1]
informTime = [0,0,0]
Output: 0Explanation: Head 1 has an inform time of 0, so both direct reports learn the news immediately. No time is needed.
Constraints:
1 <= n <= 1000000 <= headID < nmanager.length == informTime.length == nmanager[headID] == -1; every other manager is an employee ID from0ton - 1.- Manager relationships form one rooted tree with head
headID. 0 <= informTime[i] <= 1000- Employees without direct reports have
informTime[i] == 0.