A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.
Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it's guaranteed that the subordination relationships have a tree structure.
The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.
The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).
Return the number of minutes needed to inform all the employees about the urgent news.
 
Example 1:
Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Example 4:
Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.

Example 5:
Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

 
Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

Difficulty: interview

Starter code:

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        

Solutions:
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(list(map(dfs, manager)))
        
            


class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(list(map(dfs, list(range(n)))))


# class Node:
#     def __init__(self, id: int, inform_t: int):
#         self.id = id
#         self.children = []
#         self.inform_t = inform_t
    
#     def __repr__(self):
#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'
    
#     def total_inform_time(self):
#         t = self.inform_t
#         if self.children:
#             t += max(ch.total_inform_time() for ch in self.children)
#         return t

# class Solution:
    
#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:
#         nodes = [None] * len(manager)
#         root = None
#         for id, man_id in enumerate(manager):
#             if nodes[id] is None:
#                 nodes[id] = Node(id, inform_time[id])
            
#             if man_id >= 0:
#                 if nodes[man_id] is None:
#                     nodes[man_id] = Node(man_id, inform_time[man_id])

#                 nodes[man_id].children.append(nodes[id])
#             else:
#                 root = nodes[id]
#         return root
    
    
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
#         root = self.build_tree(manager, inform_time)
#         return root.total_inform_time()
    

# Top down
# class Solution:
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
#         children = [[] for _ in range(n)]
#         for id, man_id in enumerate(manager):
#             if man_id >= 0:
#                 children[man_id].append(id)
        
#         def dfs(id):
#             t = inform_time[id]
#             if children[id]:
#                 t += max(dfs(ch) for ch in children[id])
#             return t
        
#         return dfs(head_id)
 
    
# Bottom up
# class Solution:
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
        
#         def dfs(id):
#             if manager[id] >= 0:
#                 inform_time[id] += dfs(manager[id])
#                 manager[id] = -1
#             return inform_time[id]
        
#         return max(dfs(id) for id in range(n))


# Bottom up with cache
class Solution:
    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
        cache = [None] * n
        
        def dfs(id):
            if cache[id]:
                return cache[id]
            
            t = inform_time[id]
            if manager[id] >= 0:
                t += dfs(manager[id])
            
            cache[id] = t
            return t
        
        return max(dfs(id) for id in range(n))





class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        
        reports = {}
        for i,e in enumerate(manager):
            if e not in reports:
                reports[e] = []
            reports[e].append(i)
                
        accum = [0]*n
        todo = [-1]
        while todo:
            curr = todo.pop()
            mxxR = 0
            if curr not in reports:
                continue
            for r in reports[curr]:
                todo.append(r)
                accum[r] += informTime[r] + accum[manager[r]]
        return max(accum)
                
            
                
        
#         talktime = {}
#         mxx = -1
#         for i,m in enumerate(manager):
#             mxx = max(mxx, self.calc(i, manager, informTime))
#         return mxx
                
#     def calc(self,e, manager, informTime):
#         if e == -1:
#             return 0
#         return informTime[e] + self.calc(manager[e], manager, informTime)
        
        


class Solution:
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = {i: [] for i in range(n)}
        for i in range(n): 
            if manager[i] >= 0:
                graph[manager[i]].append(i)
                
        to_inform = deque([(headID, 0)])
        max_t = 0
        while to_inform:
            mid, t = to_inform.pop()
            new_t = t + informTime[mid]
            max_t = max(max_t, new_t)
            for s in graph[mid]:
                to_inform.append((s, new_t))
            
        return max_t

class Node:
    def __init__(self, val):
        self.val = val
        self.subordinates = []


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = [Node(t) for t in informTime]

        root = None
        for k, v in enumerate(manager):
            if v >= 0:
                nodes[v].subordinates.append(nodes[k])
            else:
                root = nodes[k]

        ans = 0

        def dfs(node, path):
            nonlocal ans
            if not node.subordinates:
                ans = max(ans, path + node.val)
                return
            for n in node.subordinates:
                dfs(n, n.val + path)

        dfs(root, root.val)

        return ans

    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]

        for k, v in enumerate(manager):
            if v >= 0:
                children[v].append(k)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]

        return dfs(headID)





class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1 and manager[0] == -1:
            return informTime[0]
        subordinates = defaultdict(list)
        for empId in range(len(manager)):
             subordinates[manager[empId]].append(empId)
        def dfs(sid,informTime):
            maxtime = 0
            for subId in subordinates[sid]:
                maxtime = max(maxtime,dfs(subId,informTime))
            return (maxtime+informTime[sid])
        return dfs(headID,informTime)
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = collections.defaultdict(set)
        for sub, mag in enumerate(manager):
            subs[mag].add(sub)
        
        heap, time = [(informTime[headID], headID)], 0
        while heap:
            time = heap[0][0]
            while heap and heap[0][0] == time:
                _, mag = heapq.heappop(heap)
                for sub in subs[mag]:
                    heapq.heappush(heap, (time + informTime[sub], sub))
        return time
        
            


  
class Solution:
    # 1152
    def numOfMinutes(self, n, headID, manager, informTime):
       # @lru_cache(None)
        def myTime(myBoss):
            if manager[myBoss] > -1:
                informTime[myBoss] += myTime(manager[myBoss])
                manager[myBoss] = -1
                
            return informTime[myBoss]
        return max(map(myTime, manager))

from collections import deque

class Solution:
    def build_graph(self, n, manager):
        graph = {i: [] for i in range(n)}
        for i, m in enumerate(manager):
            if m == -1:
                continue
            graph[m].append(i)
        return graph
            
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = self.build_graph(n, manager)
        if not graph[headID]:
            return 0
        
        queue = deque([(headID, informTime[headID])])
        t = 0
        informed = set()
        while queue:
            boss, time = queue.popleft()
            t = max(t, time)
            for employee in graph[boss]:
                if employee in informed:
                    continue
                queue.append((employee, time + informTime[employee]))
                informed.add(employee)
        return t

# class Node:
#     def __init__(self, id: int, inform_t: int):
#         self.id = id
#         self.children = []
#         self.inform_t = inform_t
    
#     def __repr__(self):
#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'
    
#     def total_inform_time(self):
#         t = self.inform_t
#         if self.children:
#             t += max(ch.total_inform_time() for ch in self.children)
#         return t

# class Solution:
    
#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:
#         nodes = [None] * len(manager)
#         root = None
#         for id, man_id in enumerate(manager):
#             if nodes[id] is None:
#                 nodes[id] = Node(id, inform_time[id])
            
#             if man_id >= 0:
#                 if nodes[man_id] is None:
#                     nodes[man_id] = Node(man_id, inform_time[man_id])

#                 nodes[man_id].children.append(nodes[id])
#             else:
#                 root = nodes[id]
#         return root
    
    
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
#         root = self.build_tree(manager, inform_time)
#         return root.total_inform_time()
    

# Top down
# class Solution:
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
#         children = [[] for _ in range(n)]
#         for id, man_id in enumerate(manager):
#             if man_id >= 0:
#                 children[man_id].append(id)
        
#         def dfs(id):
#             t = inform_time[id]
#             if children[id]:
#                 t += max(dfs(ch) for ch in children[id])
#             return t
        
#         return dfs(head_id)
 
    
# Bottom up
class Solution:
    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
        
        def dfs(id):
            if manager[id] >= 0:
                inform_time[id] += dfs(manager[id])
                manager[id] = -1
            return inform_time[id]
        
        return max(dfs(id) for id in range(n))


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        #           headID
        #         /        \\
        #      sub1         sub2
        #      / \\          / \\
        #   sub11 sub12  sub21 sub22
        
        subs = [[] for i in range(n)]
        for i, m in enumerate (manager):
            if m != -1:
                subs[m].append(i)
                
        def my_dfs(root):
            
            if subs[root] is None: return informTime[root]
            
            return max([my_dfs(s) for s in subs[root]] or [0]) + informTime[root]
        
        return my_dfs(headID)
            
        
        
#     def numOfMinutes(self, n, headID, manager, informTime):
#         children = [[] for i in xrange(n)]
#         for i, m in enumerate(manager):
#             if m >= 0: children[m].append(i)

#         def dfs(i):
#             return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
#         return dfs(headID)

    # def dfs(i):
    #         if manager[i] != -1:
    #             informTime[i] += dfs(manager[i])
    #             manager[i] = -1
    #         return informTime[i]
    #     return max(map(dfs, range(n)))


class Solution:
    def __init__(self):
        self.res = 0
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = defaultdict(set) 
        for i, m in enumerate(manager):
            graph[m].add(i)
        def helper(emp, time):
            if emp not in graph:
                self.res = max(self.res, time)
                return
            for e in graph[emp]:
                helper(e, time + informTime[emp])
        helper(headID, 0)
        return self.res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

        children = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
#         DFS
        def dfs(employee):
            if manager[employee] != -1:
                informTime[employee] += dfs(manager[employee])
                manager[employee] = -1
            return informTime[employee]
        return max(list(map(dfs, list(range(n)))))
#         BFS
#         companyTree = defaultdict(list)
        
#         for idx, head in enumerate(manager):
#             if head != -1:
#                 companyTree[head].append(idx)
#         # use heap 
#         queue = deque([(headID, 0)])
#         visited = set()
#         res = 0
        
#         while queue and len(visited) < n:
#             cur_employee, cur_total = queue.popleft()
#             res = max(res, cur_total + informTime[cur_employee])
#             for subord in companyTree[cur_employee]:
#                 queue.append((subord, cur_total + informTime[cur_employee]))
#         return res


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1:
            return 0
        res = 0
        childs = defaultdict(list)
        for idx, parent in enumerate(manager):
            childs[parent].append(idx)

        queue = deque([(headID, informTime[headID])])
        while queue:
            cur_id, cur_time = queue.popleft()
            # calculate max
            res = max(res, cur_time)
            for child in childs[cur_id]:
                queue.append((child, cur_time + informTime[child]))
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # create graph
        graph = collections.defaultdict(list)
        for idx, mgr in enumerate(manager):
            if idx == headID:
                continue 
                
            graph[mgr].append(idx)
        
        max_time = 0
        def dfs(start):
            nonlocal max_time
            if start is None:
                return 0
        
            curr_time = 0
            for child in graph[start]:
                curr_time = max(curr_time, dfs(child))
                
            max_time = max(max_time, curr_time + informTime[start])
            
            return curr_time + informTime[start]
        
        dfs(headID)
        
        return max_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        employees_of_manager = [[] for i in range(n)]
        for e, m in enumerate(manager):
            # print(m)
            if m >= 0: 
                employees_of_manager[m].append(e)

        def dfs(i):
            return max([dfs(j) for j in employees_of_manager[i]] or [0]) + informTime[i]
        return dfs(headID)

def createGraph(manager: List[int]):
    graph = collections.defaultdict(set)
    for i, employee in enumerate(manager):
        graph[employee].add(i)
    return graph

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = createGraph(manager)
        stack = [(0, headID)]
        ans = 0
        while stack:
            depth, employeeId = stack.pop()
            if manager[employeeId] != -1:
                informTime[employeeId] += informTime[manager[employeeId]]
            ans = max(informTime[employeeId], ans)
            for employee in graph[employeeId]:
                stack.append((depth+1, employee))
        return ans

class Solution:
    def build_graph(self,n,manager,informTime,headID):
        
        graph={x:[] for x in range(n)}
        
        for i in range(n):

            mgr=manager[i]
            emp=i
            
            if mgr == -1: continue
            
            if graph.get(mgr,0):
                graph[mgr].append(emp)
            else:
                graph[mgr]=[emp]
        
        return graph
    def traverse_graph(self, graph, headID, informTime):
        result=0
        
        for v in graph[headID]:
            result = max(result, self.traverse_graph(graph, v, informTime));
        
        return result+informTime[headID]
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph=self.build_graph(n,manager,informTime, headID)
        return self.traverse_graph(graph, headID, informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        delays = [-1] * n
        
        def delay(id: int):
            if delays[id] >= 0:
                return delays[id]
            
            myman = manager[id]
            if myman < 0:
                delays[id] = 0
                return 0
            
            mandelay = delay(myman) + informTime[myman]
            delays[id] = mandelay
            return delays[id]
        
        return max(delay(i) for i in range(n))
            

            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        def dfs(employee, time):
            self.result = max(self.result, time)
            for sub in subordinates[employee]:
                dfs(sub, time + informTime[employee])
            
        subordinates = collections.defaultdict(list)
        self.result = 0
        for i, m in enumerate(manager):
            if i != headID:
                subordinates[m].append(i)
        dfs(headID, 0)
        return self.result
            
        
    # def dfs(self, id):
    #     return max(informTime[id] + self.dfs(sub) for sub in subordinates[id]) if id in subordinates else 0


def createGraph(manager: List[int]):
    graph = collections.defaultdict(set)
    for i, employee in enumerate(manager):
        graph[employee].add(i)
    return graph

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = createGraph(manager)
        stack = [(0, headID)]
        visited = set()
        while stack:
            depth, employeeId = stack.pop()
            if employeeId not in visited:
                visited.add(employeeId)
                if manager[employeeId] != -1:
                    informTime[employeeId] += informTime[manager[employeeId]]
                for employee in graph[employeeId]:
                    stack.append((depth+1, employee))
        return max(informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = {i:[] for i in range(n)}
        for child, parent in enumerate(manager):
            if parent >= 0:
                children[parent].append(child)
        
        def dfs(i):
            return max([dfs(child) for child in children[i]], default=0) + informTime[i]
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = defaultdict(list)
        
        for i in range(len(manager)):
            graph[manager[i]].append((informTime[i], i))
        heap = [(informTime[headID], headID)]
        # dic = {}
        mx = -1
        while heap:
            time, index = heapq.heappop(heap)
            mx = max(mx,time)

            for t,n in graph[index]:
                heapq.heappush(heap, (t+time, n))
        return mx#max(dic.values())



class Solution:
    def findLongestPath(self, tree, root, informTime):
        return max([self.findLongestPath(tree, child, informTime) for child in tree[root]] + [0]) + informTime[root]
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        mapM2E = collections.defaultdict(list)
        for i in range(n):
            if i == headID:
                continue
            else:
                mapM2E[manager[i]].append(i)
        
        return self.findLongestPath(mapM2E, headID, informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager2employee = defaultdict(list)
        for employee, manager in enumerate(manager):
            manager2employee[manager].append(employee)
        
        def dfs(manager):
            if not manager2employee[manager]:
                return 0
            return max([informTime[manager] + dfs(e) for e in manager2employee[manager]])
        return dfs(headID)

from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        res = 0
        nextdict = defaultdict(set)
        timedict = []
        for i1, m in enumerate(manager):
            nextdict[m].add(i1)
        for t in informTime:
            timedict.append(t)
        
        visit = set()
        q = [(headID, 0)]
        while q:
            this = q[-1]
            visit.add(this[0])
            flag = False
            for nexte in nextdict[this[0]]:
                if nexte not in visit:
                    q.append((nexte, this[1]+timedict[this[0]]))
                    flag = True
                    break
            if not flag:
                res = max(res, q.pop()[1])
        return res
        


# class Node:
#     def __init__(self, id: int, inform_t: int):
#         self.id = id
#         self.children = []
#         self.inform_t = inform_t
    
#     def __repr__(self):
#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'
    
#     def total_inform_time(self):
#         t = self.inform_t
#         if self.children:
#             t += max(ch.total_inform_time() for ch in self.children)
#         return t

# class Solution:
    
#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:
#         nodes = [None] * len(manager)
#         root = None
#         for id, man_id in enumerate(manager):
#             if nodes[id] is None:
#                 nodes[id] = Node(id, inform_time[id])
            
#             if man_id >= 0:
#                 if nodes[man_id] is None:
#                     nodes[man_id] = Node(man_id, inform_time[man_id])

#                 nodes[man_id].children.append(nodes[id])
#             else:
#                 root = nodes[id]
#         return root
    
    
#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
#         root = self.build_tree(manager, inform_time)
#         return root.total_inform_time()
    

class Solution:
    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
        children = [[] for _ in range(n)]
        for id, man_id in enumerate(manager):
            if man_id >= 0:
                children[man_id].append(id)
        
        def dfs(id):
            t = inform_time[id]
            if children[id]:
                t += max(dfs(ch) for ch in children[id])
            return t
        
        return dfs(head_id)


class Solution:
    res = 0
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if not manager or not informTime: return 0
        dic = {-1: [[headID, informTime[headID]]]}
        for i in range(len(manager)):
            if manager[i] not in dic:
                dic[manager[i]] = []
            dic[manager[i]].append([i, informTime[i]])
        
        def dfs(dic: {}, id: int, cur: int) -> None:
            if id not in dic:
                self.res = max(self.res, cur);
                return
            
            for employee in dic[id]:
                dfs(dic, employee[0], cur + employee[1])
            
        dfs(dic, -1, 0)
        
        return self.res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        time = [-1] * n
        time[headID] = 0
        result = 0
        
        for i in range(n):
            if time[i] == -1:
                # search down a path
                index = i
                path = []
                
                while time[index] == -1:
                    path.append(index)
                    index = manager[index]
                
                for j in reversed(path):
                    time[j] = time[manager[j]] + informTime[manager[j]]
                    result = max(result, time[i])
            
        return result

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        import heapq
        uninformed = set([i for i in range(n)])
        q = [(0,headID)]
        heapq.heapify(q)
        sub = collections.defaultdict(list)
        for i,v in enumerate(manager):
            sub[v].append(i)
        while q:
            # print(q)
            # print(uninformed)
            TI, ID = heapq.heappop(q)
            uninformed -= set([(ID)])
            if not uninformed: return TI
            for sb in sub[ID]:
                if sb in uninformed: heapq.heappush(q,(TI+informTime[ID],sb))
        return -1


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        
        for i, managerId in enumerate(manager):
            graph[managerId].append((informTime[i], i))
        
        dist = {}
        heap = [(informTime[headID], headID)] 
        
        while heap:
            time, u = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = time    
            for w, v in graph[u]:
                if v in dist:
                    continue
                heapq.heappush(heap, (time+w, v))    
        return max(dist.values()) 

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        return self.DFS(n, headID, manager, informTime)

        
    def BFS(self, n: int, headID: int, manager: List[int], informTime: List[int]):
        graph = defaultdict(list)
        for i in range(n):
            graph[manager[i]].append((i, informTime[manager[i]]))
        
        q = deque([(headID, 0)])
        max_time = 0
        while q:
            node, t = q.popleft()
            max_time = max(max_time, t)
            for sub_ord, inform_time in graph[node]:
                q.append((sub_ord, inform_time + t))
        
        return max_time
    
    def DFS(self, n, headID, manager, informTime):
        graph = defaultdict(list)
        for i in range(n):
            graph[manager[i]].append((i, informTime[manager[i]]))

        def DFS_helper(node, graph, cur_time):
            nonlocal max_time

            max_time = max(max_time, cur_time)
            for sub_ord, inform_time in graph[node]:
                DFS_helper(sub_ord, graph, cur_time + inform_time)
                

            
        max_time = 0
        DFS_helper(headID, graph, 0)
        return max_time
        
        
        
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = defaultdict(list)
        for i in range(len(manager)):
            graph[manager[i]].append(i)  
        q = deque([(headID, 0)])
        res = 0
        while q:
            node, time = q.popleft()
            res = max(res, time)
            for nei in graph[node]:
                q.append((nei, time + informTime[node]))
        
        return res
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinates = collections.defaultdict(list)
        self.res = 0
        for i, v in enumerate(manager):
            subordinates[v].append(i)
        
        def dfs(manager, time):
            self.res = max(self.res, time)
            for subordinate in subordinates[manager]:
                dfs(subordinate, time + informTime[manager])
        dfs(headID, 0)        
        return self.res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        time = [-1 for _ in range(n)]
        time[headID] = 0
        result = 0
        for i in range(n):
            if time[i] == -1:
                index = i
                path = []
                while time[index] == -1:
                    path.append(index)
                    index = manager[index]
                for employee in reversed(path):
                    time[employee] = time[manager[employee]] + informTime[manager[employee]]
            result = max(result, time[i])
        return result            
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adjacency = collections.defaultdict(list)
        for i, manager_id in enumerate(manager):
            adjacency[manager_id].append(i)

        result = 0

        def traverse(worker_id, time):
            nonlocal result
            time += informTime[worker_id]
            result = max(result, time)
            list(map(lambda x: traverse(x, time), adjacency[worker_id]))

        traverse(headID, 0)
        return result

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        hierarchy = defaultdict(set)
        for index,higher in enumerate(manager):
            hierarchy[higher].add(index)##be careful about what variables you add.
        times = defaultdict(int)
        def computeTotalTime(start):
            if start in times:
                return times[start]
            else:
                answer = 0
                for lower in hierarchy[start]:
                    answer = max(answer,computeTotalTime(lower))
                answer += informTime[start]
                times[start] = answer
                return answer
        return computeTotalTime(headID)

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(n):
            if n not in tree:
                return 0
            return informTime[n] + max(dfs(k) for k in tree[n])
            
        tree = defaultdict(list)
        for i, v in enumerate(manager):
            if v == -1:
                continue
            tree[v].append(i)
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager_employee_dict = {}
        for i in range(n):
            m = manager[i] # manager of i is n
            if m != -1:
                if m in manager_employee_dict:
                    manager_employee_dict[m].append(i)
                else:
                    manager_employee_dict[m] = [i]
        
        # want to start with the head node to get the max depth
        def chain_length(em):
            if em not in manager_employee_dict:
                return 0
            return informTime[em] + max(chain_length(em_n) for em_n in manager_employee_dict[em])
        if len(manager_employee_dict) == 0:
            return 0
        # num = max(chain_length(e) for e in manager_employee_dict)
        return chain_length(headID)
        
        
                    


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinates = collections.defaultdict(list)
        for idx,man in enumerate(manager):
            subordinates[man].append(idx)
        from collections import deque
        queue = deque()
        queue.append((headID, 0))
        ans = 0
        while queue:
            node,time = queue.popleft()
            ans = max(ans, time)
            for sub in subordinates[node]:
                queue.append((sub, time+informTime[node]))
        return ans

from collections import defaultdict, deque

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = defaultdict(list)
        
        for e, m in enumerate(manager):
            graph[m].append(e)
        
        res = 0
        
        queue = deque([(headID, informTime[headID])])
        
        while queue:
            size = len(queue)
   
            employee, time = queue.popleft()
            res = max(res, time)
            if employee in graph:
                for nei in graph[employee]:
                    queue.append((nei, time + informTime[nei]))
            
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        
        for index, m in enumerate(manager):
            if m >= 0:
                children[m].append(index)
        
        def dfs(ID):
            if children[ID]:
                return max(dfs(j) for j in children[ID]) + informTime[ID]
            
            return informTime[ID]
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        def dfs(emp_id):
            
            # no subordinates
            if not graph[emp_id]:
                return 0
            max_path = float('-inf')
            for subordinate, time in graph[emp_id]:
                max_path = max(max_path, time+dfs(subordinate))
            return max_path
        
        # create graph from boss -> [(emp,informtime)]
        graph = collections.defaultdict(list)
        for emp, boss in enumerate(manager):
            graph[boss].append((emp,informTime[boss]))
        del graph[-1]
        return dfs(headID)

from typing import List
from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager_dict = defaultdict(list)
        for index, curr_manager in enumerate(manager):
            manager_dict[curr_manager].append(index)

        return self.dfs_num_of_minutes(headID, manager_dict, informTime)

    def dfs_num_of_minutes(self, curr_id, manager_dict, informTime):
        curr_inform_time = informTime[curr_id]

        direct_report_informa_time = 0
        for direct_report in manager_dict.get(curr_id, []):
            direct_report_informa_time = max(direct_report_informa_time, self.dfs_num_of_minutes(direct_report, manager_dict, informTime))
        
        return curr_inform_time + direct_report_informa_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(id: int) -> int:
            return max(informTime[id] + dfs(sub) for sub in subordinates[id]) if id in subordinates else 0
        
        subordinates = collections.defaultdict(list)
        for i, m in enumerate(manager):
            if i != headID:  #instead of m != -1
                subordinates.setdefault(m,[]).append(i)
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        
        for index, m in enumerate(manager):
            if m >= 0:
                children[m].append(index)
        
        def dfs(ID):
            return max([dfs(j) for j in children[ID]] or [0]) + informTime[ID]
        
        return dfs(headID)

from collections import deque
class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        memo = [None] * n
        memo[headID] = 0
        for uid in range(n):
            self.dfs(uid, manager, informTime, memo)
        return max(memo)
    
    def dfs(self, uid, manager, informTime, memo):
        if memo[uid] is not None:
            return memo[uid]
        
        memo[uid] = self.dfs(manager[uid], manager, informTime, memo) + informTime[manager[uid]]
        return memo[uid]

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

        # M[m] = list of employees reporting to m
        M = [[] for m in range(n)]
        for i, m in enumerate(manager):
            if m == -1:
                continue
            M[m].append(i)

        def dfs(id, t):
            t_after_informed = t + informTime[id]
            return max(dfs(sub_id, t_after_informed) for sub_id in M[id]) if M[id] else t_after_informed

        return dfs(headID, 0)



class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        managerGraph = collections.defaultdict(list)
        
        for i, v in enumerate(manager):
            managerGraph[v].append(i)
            
        res = 0
        queue = collections.deque([(headID, 0)])
        while queue:
            node, time = queue.popleft()
            res = max(res, time)
            for nei in managerGraph[node]:
                queue.append((nei, time + informTime[node]))
                
        return res

from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        def group_by_manager(l):
            d = defaultdict(lambda: [])
            
            for ind, manager in l:
                d[manager].append(ind)
            return d
        
        manager_to_subs = group_by_manager(enumerate(manager))
        def get_children(m):
            return manager_to_subs.get(m, [])
        # calculate the maximum path as the max of all the max paths of the subtrees
        def max_path(r):
            children = get_children(r)
            return informTime[r] + (max(max_path(c) for c in children) if children else 0)
        
        return max_path(headID)

from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        res = 0
        nextdict = defaultdict(set)
        timedict = defaultdict(int)
        for i1, m in enumerate(manager):
            nextdict[m].add(i1)
        for i1, t in enumerate(informTime):
            timedict[i1] = t
        
        visit = set()
        q = [(headID, 0)]
        while q:
            this = q[-1]
            visit.add(this[0])
            flag = False
            for nexte in nextdict[this[0]]:
                if nexte not in visit:
                    q.append((nexte, this[1]+timedict[this[0]]))
                    res = max(res, this[1]+timedict[this[0]])
                    flag = True
                    break
            if not flag:
                q.pop()
        return res
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def helper(boss_to_sub, informTime, start):
            return informTime[start] + max(helper(boss_to_sub, informTime, i) for i in boss_to_sub[start] ) if boss_to_sub[start] else 0
        boss_to_sub = defaultdict(list)
        for i, m in enumerate(manager):
            boss_to_sub[m].append(i)
        del boss_to_sub[-1]
        return helper(boss_to_sub, informTime, headID)
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        g = collections.defaultdict(set)
        for e, m in enumerate(manager):
            g[m].add(e)
            
        visited = dict()
        def dfs(node):
            #if node == n  or informTime[node] == n:
            #    return 0
            
            total = 0
            for nei in g[node]:
                total = max(total, dfs(nei) + informTime[node])
            return total
        
        return dfs(headID)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        children = [[] for _ in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: 
                children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        @lru_cache(None)
        def helper(emp):
            if manager[emp]>=0:
                informTime[emp]+=helper(manager[emp])
                manager[emp]= -1
            return informTime[emp]
        return max(map(helper,manager))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        
        
        # my solution ... 1744 ms ... 48 % ... 68.7 MB ... 0 %
        #  time: O(n)
        # space: O(n)
        
        def func(parent, t):
            tt = t + informTime[parent]
            self.res = max(self.res, tt)
            for child in subs[parent]:
                func(child, tt)
        
        subs = collections.defaultdict(set)
        for i,m in enumerate(manager):
            if m != -1:
                subs[m].add(i)
        self.res = 0
        func(headID, 0)
        return self.res
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        m = collections.defaultdict(list)
        for sub, mag in enumerate(manager):
            m[mag].append(sub)
        
        def dfs(i):
            if not m[i]:
                return informTime[i]
            return max(dfs(j) for j in m[i]) + informTime[i]
        return dfs(headID)
        
        
        
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(list(map(dfs, list(range(len(manager))))))
        
            


# class Solution:
#     def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
# #BFS
#         stack = [(headID, 0)]
        
#         ans = 0
#         dic = {}
#         for e, m in enumerate(manager):
#             dic[m] = dic.get(m, set())
#             dic[m].add(e)
            
#         while stack:
#             em, time = stack.pop()
#             if informTime[em] == 0:
#                 ans = max(ans, time)
#             else:
#                 for e in dic.get(em, []):
#                     stack.append((e, informTime[em]+ time))
#         return ans

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        
        for i, managerId in enumerate(manager):
            graph[managerId].append((informTime[i], i))
        
        dist = {}
        heap = [(informTime[headID], headID)] 
        
        while heap:
            time, u = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = time    
            for w, v in graph[u]:
                if v in dist:
                    continue
                heapq.heappush(heap, (time+w, v))    
        return max(dist.values()) 

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.children = []

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        # max sum path
        
        # # O(N^2)
        # def build_tree(root_id):
        #     node = TreeNode(informTime[root_id])
        #     for idx, m in enumerate(manager):
        #         if m == root_id:
        #             node.children.append(build_tree(idx))
        #     return node
                
        # O(N)
        nodes = []
        
        for idx, _ in enumerate(manager):
            nodes.append(TreeNode(informTime[idx]))
            
        for idx, m in enumerate(manager):
            if idx != headID:
                nodes[m].children.append(nodes[idx])
        
        # root
        root = nodes[headID]
        
        # O(N) time, O(1) space
        path_sum = 0
        max_path_sum = 0
        
        def dfs(node):            
            nonlocal path_sum
            nonlocal max_path_sum
            
            if not node.children:                
                max_path_sum = max(max_path_sum, path_sum + node.val)
                return
            
            for child in node.children:                
                path_sum += node.val                
                dfs(child)
                path_sum -= node.val
                
        dfs(root)
        
        return max_path_sum
            
            
            
            
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = [{} for _ in range(n)]
        for u, v in enumerate(manager):
            if v != -1:
                graph[v][u] = informTime[v]
        # print(graph)
        dist = {}
        pq = [(0, headID)]
        dist[headID] = 0
        while pq:
            t, node = heapq.heappop(pq)
            for nei in graph[node]:
                if nei not in dist or graph[node][nei] + t < dist[nei]:
                    dist[nei] = graph[node][nei] + t
                    heapq.heappush(pq, (dist[nei], nei))
        return max(dist.values())
        


import heapq

from collections import defaultdict, deque


class Solution(object):
    def numOfMinutes(self, n, headID, manager, informTime):
        if not manager or not informTime: return 0
        sub = defaultdict(list)
        q = [(0, headID)]
        heapq.heapify(q)
        used = {}
        for i in range(len(manager)):
            sub[manager[i]].append(i)
        while q:
            spent, emp = heapq.heappop(q)
            if used.get(emp, -1) != -1: continue
            used[emp] = spent
            for next_emp in sub[emp]:
                if used.get(next_emp, -1) == -1:
                    heapq.heappush(q, (spent + informTime[emp], next_emp))
        return max(used.values())

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

        def dfs(node, currTime):
            nonlocal ans
            
            if node not in graph:
                ans = max(ans, currTime)
            
            for nei in graph[node]:
                dfs(nei, currTime + informTime[node])
        
        graph = defaultdict(list)
        for u, v in enumerate(manager):
            graph[v].append(u)
 
        ans = 0
        dfs(headID, 0)
        return ans


from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        sub = defaultdict(list)
        for i, s in enumerate(manager):
            sub[s] += [i]
        
        def dfs(cur, tot):
            if cur not in sub:
                return tot
            high = max(dfs(employee, tot) + informTime[cur] for employee in sub[cur])
            return tot + high
        return dfs(headID, 0)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        tree = collections.defaultdict(list)
        for employee, manager in enumerate(manager):
            if employee != headID:
                tree[manager].append(employee)
        
        def _maxDepth(node, dist):
            if node not in tree:
                return 0
            
            return max(_maxDepth(child, informTime[child]) for child in tree[node]) + dist
        
        return _maxDepth(headID, informTime[headID])

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
#         res = 0
#         graph = defaultdict(list)
#         for index, parent in enumerate(manager):
#             graph[parent].append(index)
        
#         queue = deque([(headID, 0)])
#         while queue:
#             curId, curTime = queue.popleft()
#             res = max(res, curTime)
#             for child in graph[curId]:
#                 queue.append((child, curTime + informTime[child]))
#         return res
        
        
        
        
        
        
        
        rst = 0
        childs = defaultdict(list)
        for idx, parent in enumerate(manager):
            childs[parent].append(idx)

        q = deque([(headID, informTime[headID])])
        while q:
            cur_id, cur_time = q.popleft()
            # calculate max
            rst = max(rst, cur_time)
            for child in childs[cur_id]:
                q.append((child, cur_time + informTime[child]))
        return rst

def inform(head, subs, informTime) -> int:
    subordinates = subs[head]
    if not subordinates:
        return 0
    return informTime[head] + max(inform(sub, subs, informTime) for sub in subordinates)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = [[] for _ in range(n)]
        for sub, man in enumerate(manager):
            if man >= 0:
                subs[man].append(sub)
        return inform(headID, subs, informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        self.output = 0
        self.informTime = informTime
        self.dic = dic = {}
        for n, i in enumerate(manager):
            if i not in dic: dic[i]=[]
            dic[i].append(n)
        
        self.helper(headID, 0)
        return self.output
    
    def helper(self, n, time):
        self.output = max(self.output, time)
        newtime = time + self.informTime[n]
        for i in self.dic.get(n,[]):
            self.helper(i, newtime)

class Solution:

    def numOfMinutes(self, n, headID, manager, informTime):
        time_when_informed = {}
        total = 0

        time_when_informed[headID] = 0

        def get_informed_time(node):
            if node in time_when_informed:
                return time_when_informed[node]
            else:
                ret = informTime[manager[node]] + get_informed_time(manager[node])
                time_when_informed[node] = ret
                return ret

        ans = 0
        for node in range(len(manager)):
            ans = max(ans, get_informed_time(node))

        return ans

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = {}
        for i in range(n):
            if i == headID:
                continue
            graph[manager[i]] = graph.get(manager[i], []) + [i]
        
        self.output = 0
        def dfs(v, time):
            # is leaf, 結算 time
            if v not in graph:
                self.output = max(self.output, time)
                return
            
            # for loop v's neighbor
            for w in graph[v]:
                dfs(w, time + informTime[v])
        
        dfs(headID, 0)
        return self.output

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # using manager make graph => Value is key, Index is value, cost is informTime[Value]
# do DFS find max
        
        graph = []
        for i in range(n):
            graph.append([])
        for i in range(len(manager)):
            if(manager[i]!=-1):
                graph[manager[i]].append(i)
        print(graph)
        # DFS
        stack =[(headID, 0)]
        cost =0
        maxi =0
        while(len(stack)):
            node, cost = stack.pop()
            cost += informTime[node]
            if(cost>maxi):
                maxi = cost
            for child in graph[node]:
                stack.append((child, cost))
        return maxi


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager_list = collections.defaultdict(list)
        for i in range(len(manager)):
            manager_list[manager[i]].append(i)
        
        queue = [(headID, informTime[headID])]
        time = 0
        while queue:
            # print(queue)
            cur, cur_time = queue.pop(0)
            time = max(time, cur_time)
            if manager_list[cur] != []:
                print((cur, informTime[cur]))
                employees = manager_list[cur]
                manager_list[cur] = []
                for employee in employees:
                    queue.append((employee, cur_time + informTime[employee]))
        return time
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node , curTime):
            nonlocal totalTime
            visited.add(node)
            totalTime = max(curTime , totalTime)
            for nextNode in graph[node]:
                if nextNode not in visited:
                    dfs(nextNode , curTime + informTime[node])
        graph = defaultdict(set)
        totalTime = 0
        visited = set()
        for u , v in enumerate(manager):
            graph[u].add(v)
            graph[v].add(u)
        visited.add(-1)
        dfs(headID , 0)
        return totalTime


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = defaultdict(lambda: [])
        for employee, m in enumerate(manager):
          children[m].append(employee)
          
        def dfs(e, total_min):
          cur_time = total_min + informTime[e] 
          if len(children[e]) == 0:
            return cur_time
          
          max_time = cur_time
          for employee in children[e]:
            max_time = max(max_time, dfs(employee, cur_time))
          return max_time
            
        return dfs(headID, 0)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def check(manager, informTime, total_time, cur):
            if total_time[cur] >= 0:
                return total_time[cur]
            if manager[cur] == -1:
                total_time[cur] = 0
                return 0
            boss = manager[cur]
            total_time[cur] = check(manager, informTime, total_time, boss) + informTime[boss]
            return total_time[cur]
            
        total_time = [-1]*n
        rtv = 0
        for i in range(n):
            rtv = max(rtv, check(manager, informTime, total_time, i))
        return rtv

from collections import defaultdict


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        max_time_needed = 0
        children = defaultdict(list)
        for i, emp in enumerate(manager):
            children[emp].append(i)
            
        stack = [(headID, informTime[headID])]
        
        while stack:
            emp_id, time_taken = stack.pop()
            max_time_needed = max(max_time_needed, time_taken)
            
            for ch in children[emp_id]:
                stack.append((ch, time_taken + informTime[ch]))
        
        return max_time_needed

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        if n == 1:
            return 0
        
        # need data structure to keep track of individual employees
        time = collections.defaultdict(int)
        
        # do some preprocessing
        # create a map worksUnder
        # id -> {ids of employees that work under this manager}
        worksUnder = collections.defaultdict(set)
        
        for i in range(n):
            # employee i works under manager[i]
            worksUnder[manager[i]].add(i)
        
        stack = [headID]
        while stack:
            managerID = stack.pop()
            for i in worksUnder[managerID]:
                    # employee i works under managerID
                    # emplyee i's time is his manager's time plus 
                    # his manager's inform time
                    time[i] = informTime[managerID] + time[managerID]
                    stack.append(i)
        
        return max(time.values())

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        q = [(headID, 0)]
        
        graph = collections.defaultdict(list)
        for i in range(n):
            if manager[i] != -1:
                graph[manager[i]].append(i)
        
        res = 0
        
        while q:
            sz = len(q)
            for _ in range(sz):
                i,t = q.pop(0)
                t += informTime[i]
                res = max(res, t)
                for j in graph[i]:
                    q.append((j, t))
        
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(len(manager)):
            if i == headID:
                continue
            graph[manager[i]].append(i)
        time = 0
        q = collections.deque([(headID, 0)])
        while q:
            node = q.popleft()
            time = max(time, node[1])
            for v in graph[node[0]]:
                q.append((v, node[1] + informTime[node[0]]))
        return time


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        max_time, time_map = 0, {}
        
        for curr in range(len(manager)):
            
            # memoization: backtracking to head or till the one we've
            # already seen before
            curr_em, curr_time = [], []
            while curr not in time_map and curr != -1:
                
                curr_em.append(curr)
                curr_time.append(informTime[curr])
                curr = manager[curr]
            
            # reconstruct the accumulated pathsum, save it in the map
            if curr_time:
                rest_time = time_map[curr] if curr != -1 else 0
                curr_time[-1] += rest_time
                time_map[curr_em[-1]] = curr_time[-1]
                for j in range(len(curr_time)-2, -1, -1):
                    curr_time[j] = curr_time[j+1] + curr_time[j]
                    time_map[curr_em[j]] = curr_time[j]
                    
                # compare every current longest pathsum with the currmax
                max_time = max(max_time, curr_time[0])
        return max_time

class Node:
    def __init__(self, val):
        self.val = val
        self.subordinates = []


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = [Node(t) for t in informTime]

        root = None
        for k, v in enumerate(manager):
            if v >= 0:
                nodes[v].subordinates.append(nodes[k])
            else:
                root = nodes[k]

        ans = 0

        def dfs(node, path):
            nonlocal ans
            if not node.subordinates:
                ans = max(ans, path + node.val)
                return
            for n in node.subordinates:
                dfs(n, n.val + path)

        dfs(root, root.val)

        return ans




class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        tree = collections.defaultdict(list)
        
        for idx, val in enumerate(manager):
            tree[val].append(idx)
        
        self.max_time = 0
        def dfs(node):
            time = 0
            for child in tree[node]:
                time = max(time, dfs(child))
            return informTime[node] + time
        
        return dfs(headID)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        managerToReports, ms = defaultdict(set), set([headID])
        for i, m in enumerate(manager): managerToReports[m].add(i)
        def dfs(parent): return max([dfs(report) for report in managerToReports[parent]] or [0]) + informTime[parent]
        return dfs(headID)

class Solution:
    # 1152 ms
    def numOfMinutes(self, n, headID, manager, informTime):
        @lru_cache(None)
        def myTime(myBoss):
            if manager[myBoss] > -1:
                informTime[myBoss] += myTime(manager[myBoss])
              #  t2 = 
                manager[myBoss] = -1
               # return t1 + t2
            return informTime[myBoss]
        return max(map(myTime, manager))

class Solution:
    class AdjList:
        def __init__(self, edges, h):
            self.manager = edges
            self.mlist = {}
            for u, v in enumerate(edges):
                
                if v == -1:
                    continue
                if u not in self.mlist:
                    self.mlist[u] = [v]
                else:
                    self.mlist[u].append(v)
                
                if v not in self.mlist:
                    self.mlist[v] = [u]
                else:
                    self.mlist[v].append(u)
            
        def adjacent(self, node):
            
            if node not in self.mlist:
                return []
            
            
            return self.mlist[node]
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        adj = Solution.AdjList(manager, headID)
        
        visited = [0]*n
        
        
        def dfs(node):
            
            visited[node] = 1
            
            
            t = 0
            for neig in adj.adjacent(node):
                
                if visited[neig] == 0:
                    temp =  dfs(neig)
                    t = max(t, temp)
                    
            return informTime[node] + t
        
        return dfs(headID)
        
        
        
        
        
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        n = len(manager)
        graph = collections.defaultdict(list)
        
        for i in range(n):
            graph[manager[i]].append(i)
                
        q = deque([(headID, 0)])
        res = 0
        
        while q:
            node, time = q.popleft()
            res = max(res, time)
            for nei in graph[node]:
                q.append((nei, time + informTime[node]))
        
        return res
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adjList = defaultdict(list)

        for i in range(n):
            # manager[i] = j so j -> i
            adjList[manager[i]].append(i)

        # starting at headID - BFS traversal
        queue = deque([(headID, 0)])

        # total time to inform
        maxTime = -1

        # manager[headID] subordinates to the CEO
        while queue:
            current, currentTime = queue.pop()
            # add all subordinates then add the time needed - repeat
            maxTime = max(maxTime, currentTime + informTime[current] )

            for employee in adjList[current]:
                queue.appendleft((employee, currentTime + informTime[current]))


        return maxTime

class Node:
    def __init__(self, val, weight=0):
        self.root = val
        self.weight = weight
        self.children = []
    
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        hashmap = {}
        
        for i in range(n):
            hashmap.update({i: Node(i)})
        
        for i, item in enumerate(manager):
            if item == -1:
                head = hashmap[i]
            else:
                hashmap[item].children.append(hashmap[i])
        
        for i, time in enumerate(informTime):
            hashmap[i].weight = time
            
        def recur(root) -> int:
            if not root.children:
                return root.weight
            
            max_time = 0
            for child in root.children:
                time = recur(child)
                if time > max_time:
                    max_time = time
            
            return root.weight + max_time
        
        return recur(head)

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        companyTree = defaultdict(list)
        
        for idx, head in enumerate(manager):
            if head != -1:
                companyTree[head].append(idx)
        # use heap 
        queue = deque([(headID, 0)])
        visited = set()
        res = 0
        
        while queue and len(visited) < n:
            cur_employee, cur_total = queue.popleft()
            res = max(res, cur_total + informTime[cur_employee])
            # visited.add(cur_employee)
            for subord in companyTree[cur_employee]:
                # if subord not in visited: 
                queue.append((subord, cur_total + informTime[cur_employee]))
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
#         dic = collections.defaultdict(list)
#         for emp,mng in enumerate(manager):
#             dic[mng].append([emp,informTime[mng]])

#         bfs = [[headID,0]]
#         ans = {}
#         while(bfs):
#             for i in range(len(bfs)):
#                 cur_mng,time = bfs.pop(0)
#                 ans[cur_mng] = time
#                 bfs += [[x,y+time] for x,y in dic[cur_mng]]
#         return max(ans.values())

        g = collections.defaultdict(list)
        for i, v in enumerate(manager):
            g[v].append(i)
        
        def dfs(i):
            return informTime[i] if not g[i] else max([informTime[i] + dfs(c) for c in g[i]])
    
        return dfs(headID)
                
    
          #         0
          #        / \\
          #       1.  2
          #     / \\. / \\
          #    3  4. 5. 6
          #   /\\  /\\ /\\   /\\
          #  7  7 8 8 9 9 10 10
        
#         8
#         0
#         [-1,5,0,6,7,0,0,0]
#         [89,0,0,0,0,523,241,519]
        
#                         0
#                      / \\ \\ \\
#                     2   5 6 7
#                        / / /  
#                       1 3 4
                        
    
# 11
# 4
# [5,9,6,10,-1,8,9,1,9,3,4]
# [0,213,0,253,686,170,975,0,261,309,337]


#                          4         686
#                           \\
#                            10      337
#                            /
#                           3        253
#                          /
#                         9          309
#                        /|\\
#                       1 6 8        975
#                      /  |  \\
#                     7   2   5      170
#                              \\
#                               0    0


from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        child_list = defaultdict(list)
        for i in range(n):
            j = manager[i]
            if j >= 0:
                child_list[j].append(i)
        
        def step(eid):
            children = child_list[eid]
            if not children:
                return 0
            
            return informTime[eid] + max(step(cid) for cid in children)
        
        return step(headID)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        def dfs(node):
            if manager[node] != -1:
                informTime[node] += dfs(manager[node])
                manager[node] = -1
            return informTime[node]
        return max(dfs(i) for i in range(n))


from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        if not manager:
            return 0
        
        #building the graph
        graph = defaultdict(list)
        for v in range(n):
            graph[manager[v]].append(v)
        
        #For each node, we have to take the hieghest time
        #returned from its subordinates/children
        def dfs(node):
            if node not in graph:
                return informTime[node]
            else:
                return  informTime[node]+max([dfs(n) for n in graph[node]])
        
        return dfs(headID)
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adj = {}
        if len(manager) == 1:
            return informTime[-1]
        for i in range(n):
            adj[i] = []
            
        for idx,i in enumerate(manager):
            if i == -1:
                continue
            adj[i].append([idx,informTime[idx]])
        # print(adj)    
        ans = [-10**10]
        def dfs(curr,cost):
            # print(curr,cost)
            ans[-1] = max(ans[-1],cost)
            for i in range(len(adj[curr])):
                # cost = adj[curr][i][1]
                dfs(adj[curr][i][0],cost+adj[curr][i][1])
            
        dfs(headID,informTime[headID])
        # print(adj)
        return ans[-1]
#         mx = -10**10
#         for k,v in adj.items():
#             for i in v:
#                 mx = max(mx,i[1])
#         return mx+informTime[headID]
            
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph=collections.defaultdict(list)
        for  i,c in enumerate(manager):
            if c!=-1:
                graph[c].append(i)
   
        
        que=[(headID,0)]
        ans=0
        while que:
            node,time=que.pop(0)
            ans=max(ans,time)
            for i in graph[node]:
                que.append((i,time+informTime[node]))
            
            
           
          
        return ans
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for idx in range(n):
            graph[manager[idx]].append(idx)
        
        max_time = 0
        queue = collections.deque([(headID, 0)])
        while queue:
            node, time = queue.popleft()
            max_time = max(max_time, time)
            for sub in graph[node]:
                queue.append((sub, time + informTime[node]))
        return max_time
        
            


class Node:
    
    def __init__(self, unique_id, information_time):
        self.information_time = information_time
        self.unique_id = unique_id
        self.childrens = []
        
    def add_child(self, child):
        self.childrens.append(child)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        root = Node(headID, informTime[headID]) # 0
        id_node_mapping = {headID: root} # {0: (0, 0)}
        
        def dfs(node):
            max_time = 0
            for child in node.childrens:
                max_time = max(dfs(child), max_time)
                
            return max_time + node.information_time
        
        for i, (parent, timetaken) in enumerate(zip(manager, informTime)):
            
            if i not in id_node_mapping:
                id_node_mapping[i] = Node(i, timetaken)
            else:
                id_node_mapping[i].information_time = timetaken
                
            if parent not in id_node_mapping:
                id_node_mapping[parent] = Node(parent, 0)
                
            id_node_mapping[parent].add_child(id_node_mapping[i])
            
        return dfs(root)


class Node:
    
    def __init__(self, unique_id, information_time):
        self.information_time = information_time
        self.unique_id = unique_id
        self.childrens = []
        
    def add_child(self, child):
        self.childrens.append(child)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        root = Node(headID, informTime[headID]) # 0
        id_node_mapping = {headID: root} # {0: (0, 0)}
        
        def dfs(node):
            max_time = 0
            for child in node.childrens:
                max_time = max(dfs(child), max_time)
                
            return max_time + node.information_time
        
        for i, (parent, timetaken) in enumerate(zip(manager, informTime)):
            
            if i == root.unique_id:
                continue
            
            if i not in id_node_mapping:
                id_node_mapping[i] = Node(i, timetaken)
            else:
                id_node_mapping[i].information_time = timetaken
                
            if parent not in id_node_mapping:
                id_node_mapping[parent] = Node(parent, 0)
                
            id_node_mapping[parent].add_child(id_node_mapping[i])
            
        return dfs(root)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(n):
            graph[manager[i]].append(i)
            
        queue = collections.deque([(headID, 0)])
        result = 0
        while queue:
            i, time = queue.pop()
            result = max(result, time)
            for j in graph[i]:
                queue.append((j, time + informTime[i]))
        return result


class Solution:
    # 1152 ms
    def numOfMinutes(self, n, headID, manager, informTime):
        @lru_cache(None)
        def myTime(myBoss):
            if manager[myBoss] > -1:
                t1 = informTime[myBoss]
                t2 = myTime(manager[myBoss])
                return t1 + t2
            return informTime[headID]
        return max(map(myTime, manager))

class Tree:
    def __init__(self):
        pass

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = {}
        
        for i,val in enumerate(manager):
            if val in graph:
                graph[val].append(i)
            else:
                graph[val] = [i]
        
        ans = BFS(headID,informTime,graph)
        return ans

def BFS(root,informTime,graph):
        queue = [(root,0)]
        maxTime = 0
        
        while(len(queue)):
            currElem = queue.pop(0)
            node = currElem[0]
            currTime = currElem[1]
            
            CurrInformTime = informTime[node]
            
            timeToNext = currTime+CurrInformTime
            maxTime = max(timeToNext,maxTime)
                    
            if node in graph:
                children = graph[node]
                for i in children:
                    queue.append((i,timeToNext))
        
        return maxTime

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = defaultdict(list)
        for i, j in enumerate(manager):
            children[j].append(i)
        
        def dfs(node):
            return informTime[node] + max([dfs(child) for child in children[node]] or [0])
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        managerToReports, ms = defaultdict(set), set([headID])
        for i, m in enumerate(manager): managerToReports[m].add(i)
        self.result = 0
        def dfs(parent, consumedTime):
                if not managerToReports[parent]: self.result = max(self.result, consumedTime)
                [dfs(report, consumedTime + informTime[parent]) for report in managerToReports[parent]]
        dfs(headID, 0)
        return self.result

from collections import defaultdict, deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(mngr):
            if not manager_map[mngr]:
                return 0
            result = 0
            result += max(inform_time + dfs(subordinate) for subordinate, inform_time in manager_map[mngr])
            return result
        manager_map = defaultdict(list)
        i = 0
        for manager_ix, time in zip(manager, informTime):
            manager_map[manager_ix].append((i, informTime[i]))
            i += 1
        
        return dfs(-1)


import heapq

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        
        graph = collections.defaultdict(list)
        for i in range(len(manager)):
            u, v, w = manager[i], i, informTime[i]
            if v == -1:
                continue
            graph[u].append((v, w))
        
        queue = [(headID, informTime[headID])]
        seen = set()
        heapq.heapify(queue)
        time = {i: float('inf') for i in range(n)}
        time[headID] = 0
        
        
        while queue and len(seen) < n:
            f, dist = heapq.heappop(queue)
            seen.add(f)
            time[f] = min(time[f], dist)
            
            for nb, w in graph[f]:
                if nb not in seen:
                    heapq.heappush(queue, (nb, dist + w))
                    
        
        maxi = max(time.values())
        
        return maxi if maxi < float('inf') else -1
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def method1():
            def dfs(node,time):
                nonlocal ans
                if node not in set(manager):
                    ans=max(ans,time)
                    return
                
                for i,m in enumerate(manager):
                    if m==node:
                        dfs(i, time+informTime[m])
                
                        
            ans=float('-inf')
            dfs(headID,0)
            return ans
        #return method1()
    
        def method2():
            children = [[] for i in range(n)]
            for i, m in enumerate(manager):
                if m >= 0: children[m].append(i)

            def dfs(i):
                return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
            return dfs(headID)
        
        return method2()

from collections import defaultdict as dd

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        m_to_s = dd(set)
        for i in range(len(manager)):
            m_to_s[manager[i]].add(i)
        stack = [(headID, 0)]
        max_time = 0
        while stack:
            employee, time = stack.pop()
            max_time = max(time, max_time)
            for subordinate in m_to_s[employee]:
                stack.append((subordinate, time + informTime[employee]))
        return max_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def method1():
            def dfs(node,time):
                nonlocal ans
                if not children[node]:
                    ans=max(ans,time)
                    return
                
                for c in children[node]:
                    dfs(c, time+informTime[node])
                
            children = [[] for i in range(n)]
            for i, m in enumerate(manager):
                if m >= 0: children[m].append(i)
                    
            ans=float('-inf')
            dfs(headID,0)
            return ans
        return method1()
    
        def method2():
            children = [[] for i in range(n)]
            for i, m in enumerate(manager):
                if m >= 0: children[m].append(i)

            def dfs(i):
                return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
            return dfs(headID)
        
        return method2()

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        time = [-1] * n
        time[headID] = 0
        result = 0
        
        for i in range(n):
            # if the index isn't visited (hasn't already been found with index=manager[index])
            if time[i] == -1:
                # search down a path
                index = i
                path = []
                
                # follows path of manager to subordinate
                while time[index] == -1:
                    path.append(index)
                    index = manager[index]
                
                # adds everything together
                for j in reversed(path):
                    time[j] = time[manager[j]] + informTime[manager[j]]
                    result = max(result, time[i])

        return result

class Node:
    def __init__(self, id):
        self.id = id
        self.children = []

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = []
        for i in range(n):
            nodes.append(Node(i))
        rootId = -1
        for i in range(n):
            if manager[i] != -1:
                nodes[manager[i]].children.append(nodes[i])
            else:
                rootId = i
        self.totalTime = 0
        def dfs(root, time):
            if not root:
                return
            self.totalTime = max(self.totalTime, time)
            for node in root.children:
                dfs(node, time + informTime[root.id])
        dfs(nodes[rootId], 0)
        return self.totalTime

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 1:
            return informTime[0]
        
        s = collections.defaultdict(list)
        for i in range(n):
            if manager[i] == -1:
                continue
            s[manager[i]].append(i)
        
        return self.maxTime(s, informTime, headID)
    
        
    def maxTime(self, employeeMap, informTime, curID):
        if not employeeMap[curID]:
            return informTime[curID]
        
        curMax = informTime[curID]
        
        for subordinate in employeeMap[curID]:
            curMax = max(curMax, informTime[curID] + self.maxTime(employeeMap, informTime, subordinate))
        
        return curMax


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node,cur_time):
            nonlocal total_time
            visited.add(node)
            total_time = max(total_time,cur_time)
            for next_node in graph[node]:
                if next_node not in visited:
                    dfs(next_node, cur_time + informTime[node])
                    
        
        
        
        
        total_time = 0
        graph = defaultdict(set)
        for u,v in enumerate(manager):
            graph[u].add(v)
            graph[v].add(u)
        visited = set()
        visited.add(-1)
        
        dfs(headID, 0)
        return total_time


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = {}
        for i,man in enumerate(manager):
            if man == -1:
                continue
            if man not in subs:
                subs[man] = set()# if man != -1 else None
            subs[man].add(i)
            
        #print(subs)
        queue = [(headID, 0, 0)]
        informTimes = {}
        
        while queue:
            curr, level, informedAt = queue.pop()
            if curr not in subs:
                continue
            emps = subs[curr]
                            
            for e in emps:
                if level not in informTimes:
                    informTimes[level] = -1
                currInformTime = informTime[curr] + informedAt
                informTimes[level] = max(informTimes[level], currInformTime)
                queue.append((e, level+1, currInformTime))
        if not informTimes:
            return 0
        
        maxInformTime = -1
        for level, informTimesLevel in list(informTimes.items()):
            maxInformTime = max(maxInformTime, informTimesLevel)
        #maxLevel = max(informTimes.keys())
        return maxInformTime


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def helper(emp):
            if manager[emp]>=0:
                informTime[emp]+=helper(manager[emp])
                manager[emp]= -1
            return informTime[emp]
        return max(map(helper,manager))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = collections.defaultdict(list)
        for i,a in enumerate(manager):
            children[a].append(i)
        def dfs(i):
            if not children[i]:
                return 0
            else:
                return informTime[i]+max(dfs(j) for j in children[i])
        return dfs(children[-1][0])


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(g, u, informTime, time):
            total_time = time
            for v in g[u]:
                if v != -1: total_time = max(total_time, dfs(g, v, informTime, time + informTime[v]))
                
            return total_time
        
        
        g = defaultdict(list)
        for i, m in enumerate(manager):
            if m != -1: g[m].append(i)
        
        return dfs(g, headID, informTime, informTime[headID])


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # ret[i] is num minutes from start until employee i knows about it
        ret = [-1]*n
        def computeFor(i):
            mana = manager[i]
            if mana == -1:
                #is head of company
                return 0
            # otherwise manager needs to learn, then informTime
            return getVal(mana) + informTime[mana]
        
        def getVal(i):
            # cached computation
            if ret[i] == -1:
                ret[i] = computeFor(i)
            return ret[i]
        
        return max(getVal(i) for i in range(n))


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 1:
            return 0
        t = 0
        m = {}
        start = None
        for i in range(len(manager)):
            if manager[i] != -1:
                if manager[i] in m:
                    m[ manager[i] ].append( i )
                else:
                    m[ manager[i] ] = [ i ]
            else:
                start = i
        q = []
        q.append((start,informTime[start]))
        hi = 0 # max value
        while (len(q) > 0):
            # print(q)
            out = q.pop(0)
            index = out[0]
            cost = out[1]
            if cost > hi: hi = cost
            if index in m:
                for i in m[index]:
                    q.append((i, cost + informTime[i]))
        
        return hi

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        for person, manag in enumerate(manager):
            if manag!=-1:
                children[manag].append(person)
        
        def dfs(node):
            return max((dfs(child) for child in children[node]),default=0)+informTime[node]
        return dfs(headID)
        


class Solution:
    def __init__(self):
        self.result = -1
        self.reports_map = defaultdict(list)
        
    def notifyReport(self, managerID: int, timeSpent: int, informTime: List[int]):
        if managerID not in self.reports_map:
            if self.result == -1 or timeSpent > self.result:
                self.result = timeSpent
        else:
            for report in self.reports_map[managerID]:
                self.notifyReport(report, timeSpent + informTime[managerID], informTime)
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        for i in range(0, len(manager)):
            self.reports_map[manager[i]].append(i)
        
        self.notifyReport(headID, 0, informTime)
        
        return self.result

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        graph = defaultdict(list)
        for i, mgr in enumerate(manager):
            graph[mgr].append(i)
        
        q = deque()
        q.append((-1, 0))
        seen = set([-1])
        ans = 0
        
        while q:
            node, cumSum = q.popleft()
            ans = max(ans, cumSum)
            for sub in graph[node]:
                if sub not in seen:
                    seen.add(sub)
                    q.append((sub, cumSum+informTime[sub]))
        return ans


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node):
            return max([dfs(j) for j in tree[node]] or [0]) + informTime[node]
        ret=[0]
        tree = defaultdict(set)
        for i, m in enumerate(manager):
            tree[m].add(i)
        return dfs(headID)

class Solution:
    class Node :
        def __init__(self, val, inform = 0) :
            self.val = val
            self.inform = inform
            self.children = []
    
    def traversal(self, root, time) -> int :
      if not root or root is None : return time
      final_time = time
      # print(root.val, root.children)
      for node in root.children :
        final_time = max(final_time, self.traversal(node, time + root.inform))
      return final_time
      
      
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        d = {}
        root = self.Node(headID)
        d[headID] = root
        
        for i in range(n) :
          if i == headID :
            d[headID].inform = informTime[i]
            continue
          d[i] = self.Node(i, informTime[i])
          
        for i,m in enumerate(manager) :
          if m == -1 : continue
          d[m].children.append(d[i])  # add reportees
#         for k,v in d.items() :
#           print(k, v.val, len(v.children))
        
        
        final_time = self.traversal(root, 0)
        return final_time
        
          
        
          


class Solution:
    def dfsFromId(self, g, visited, informTime, vertex, times, currTime):
        visited[vertex] = True
        times[0] = max(times[0], currTime)
        for to in g[vertex]:
            if not visited[to]:
                self.dfsFromId(g, visited, informTime, to, times, currTime + informTime[vertex])
        
        
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        g = [set() for i in range(n)]
        visited = [False] * n
        maxMinutes = [0]
        
        for i,v in enumerate(manager): g[v].add(i)
            
        self.dfsFromId(g, visited, informTime, headID, maxMinutes, 0)
                
        return maxMinutes[0]

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager_sub = defaultdict(list)
        for e, m in enumerate(manager):
            manager_sub[m].append(e)
        
        res = 0
        def max_inform_time(employee, initial_time):
            subordinate_time = []
            
            for e in manager_sub[employee]:
                t = max_inform_time(e, initial_time + informTime[e])
                subordinate_time.append(t)
            
            return max(subordinate_time) if subordinate_time else initial_time

        return max_inform_time(headID, informTime[headID])
    


from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        
        return max(list(map(dfs, list(range(n)))))


from collections import *
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        mapper = defaultdict(list)
        for i, man in enumerate(manager):
            mapper[man].append(i)
        queue = [(headID,informTime[headID])]
        vis = set()
        ans = 0
        while queue:
            iden, time = queue.pop(0)
            ans = max(ans,time)
            vis.add(iden)
            for sub in mapper[iden]:
                if sub not in vis:
                    queue.append((sub, time + informTime[sub]))
        return ans

from collections import deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        graph = {}
        
        if len(manager) == 1:
            return 0
        
        for emp,manager in enumerate(manager):
            if emp == headID:
                continue
            if manager in graph:
                graph[manager].append(emp)
            else:
                graph[manager] = [emp]
                
        ans = {}
        
        ans[headID] = 0
        
        Queue = deque()
        Queue.append(headID)
        
        maxTime = 0
        while Queue:
            man = Queue.popleft()  
            if man not in graph:
                continue
            for emp in graph[man]:
                ans[emp] = ans[man] + informTime[man]
                maxTime = max(maxTime, ans[emp])
                Queue.append(emp)
                
        return maxTime

from collections import deque


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        class TreeNode():
            def __init__(self, time=0):
                self.children = []
                self.time = time

        tree_nodes = [None for _ in range(n)]
        for index in range(n):
            # Set up child
            if tree_nodes[index] is None:
                tree_nodes[index] = TreeNode(time=informTime[index])
                
            # Set up parent
            if manager[index] != -1:
                if tree_nodes[manager[index]] is None:
                    tree_nodes[manager[index]] = TreeNode(time=informTime[manager[index]])

                tree_nodes[manager[index]].children.append(index)
                
            
        def BFS(root: TreeNode) -> int:
            longest_time = 0
            queue = deque()
            queue.append(root)
            
            while len(queue):
                node = queue.popleft()
                
                longest_time = max(longest_time, node.time)
                
                for child in node.children:
                    tree_nodes[child].time += node.time
                    queue.append(tree_nodes[child])
                    
            return longest_time
        
        return BFS(tree_nodes[headID])
            
        ##############################
        
        def sum_leaf_to_root(leaf: int) -> int:
            if leaf == headID:
                return informTime[headID]
            
            boss = manager[leaf]
            total_time = 0
            
            while boss != headID:
                total_time += informTime[boss]
                boss = manager[boss]
                
            total_time += informTime[headID]
            
            return total_time
        
        return max(
            sum_leaf_to_root(leaf)
            for leaf in (
                index
                for index in range(len(manager))
                if index not in manager
            )
        )

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        sub_h = {}
        for idx in range(n):
            if idx==headID: continue
            if manager[idx] not in sub_h: sub_h[manager[idx]] = [informTime[manager[idx]], idx]
            else: sub_h[manager[idx]].append(idx)
        self.res = 0
        
        def helper(cur, t):
            if cur not in sub_h: 
                self.res = max(self.res, t)
                return
            for sub in sub_h[cur][1:]:
                helper(sub, t+sub_h[cur][0])
                
        helper(headID, 0)
        return self.res
        



class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(dfs(i) for i in range(n))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        org = collections.defaultdict(list)
        self.res = 0
        
        for i, v in enumerate(manager):
            org[v].append(i)
        
        def dfs(manager, time):
            self.res = max(self.res, time)
            for sub in org[manager]:
                dfs(sub, time + informTime[sub])
        
        dfs(headID, informTime[headID])
        return self.res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        stack = [(headID, 0)]
        
        ans = 0
        dic = {}
        for e, m in enumerate(manager):
            dic[m] = dic.get(m, set())
            dic[m].add(e)
        while stack:
            em, time = stack.pop(0)
            if informTime[em] == 0:
                ans = max(ans, time)
            else:
                for e in dic.get(em, []):
                    stack.append((e, informTime[em]+ time))
        return ans
            
        
        
        
        ##O(n), O(n)两种方法
        
        
        
        
        
#         manage = {}
#         for i in range(n):
#             manage[manager[i]] = manage.get(manager[i], []) + [i]
            
#         ans = 0
#         stack = [(headID,0)]

#         while stack:
#             node, time = stack.pop()
#             if informTime[node] == 0:
#                 ans = max(ans, time)
#             else:
#                 for nei in manage[node]:
#                     stack.append((nei, informTime[node] + time))
            
#         return ans


class Solution:
    # 1152 ms
    def numOfMinutes(self, n, headID, manager, informTime):
       # @lru_cache(None)
        def myTime(myBoss):
            if manager[myBoss] > -1:
                informTime[myBoss] += myTime(manager[myBoss])
              #  t2 = 
                manager[myBoss] = -1
               # return t1 + t2
            return informTime[myBoss]
        return max(map(myTime, manager))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        
        employeesDict = {}
        
        for i in range(0, len(manager)): 
            
            if manager[i] == -1: 
                continue
            
            if manager[i] in employeesDict: 
                employeesDict[manager[i]].append(i)
            else:
                l = []
                l.append(i)
                employeesDict[manager[i]] = l

    
        return self.helper(headID, informTime[headID], employeesDict, informTime)
    
    
    def helper(self, currEmp, currTime, employeesDict, informTime):

        if currEmp not in employeesDict: 
            return currTime
        newTime = -1
        managerList = employeesDict[currEmp]
        for i in range(0, len(managerList)):

            newTime = max(newTime, self.helper(managerList[i], informTime[managerList[i]], employeesDict, informTime) + currTime)

        return newTime

            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = {}
        for i,man in enumerate(manager):
            if man == -1:
                continue
            if man not in subs:
                subs[man] = set()# if man != -1 else None
            subs[man].add(i)
            
        #print(subs)
        queue = [(headID, 0, 0)]
        informTimes = {}
        
        while queue:
            curr, level, informedAt = queue.pop()
            if curr not in subs:
                continue
            emps = subs[curr]
                            
            for e in emps:
                if level not in informTimes:
                    informTimes[level] = -1
                currInformTime = informTime[curr] + informedAt
                informTimes[level] = max(informTimes[level], currInformTime)
                queue.append((e, level+1, currInformTime))
        if not informTimes:
            return 0
        
        return max(informTimes.values())


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        tree = collections.defaultdict(list)
        
        for idx, val in enumerate(manager):
            tree[val].append(idx)
        
        self.max_time = 0
        def dfs(node, time):
            new_time = time + informTime[node]
            self.max_time = max(self.max_time, new_time)
            for child in tree[node]:
                dfs(child, new_time)
        dfs(headID, 0)
        return self.max_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        adj = defaultdict(list)
        
        for i in range(n):
            adj[manager[i]].append(i)

        def dfs(n: int) -> int:
            return informTime[n] + max([dfs(nn) for nn in adj[n]] or [0])
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        self.employee = collections.defaultdict(list)
        self.time = 0
        self.infromTime = informTime
        
        for i, m in enumerate(manager):
            self.employee[m].append(i)
        
        self.dfs(headID, informTime[headID])
        
        return self.time
        
    def dfs(self, rootID, time):
        self.time = max(time, self.time)
        
        for employee in self.employee[rootID]:
            self.dfs(employee, time+self.infromTime[employee])

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def helper(i, manager, informTime):
            if manager[i] != -1:
                informTime[i] += helper(manager[i], manager, informTime)
                manager[i] = -1
            return informTime[i]
            
        res = 0
        for i in range(n):
            res = max(res, helper(i, manager, informTime))
        return res

class Node:
    def __init__(self,id,time):
        self.id = id
        self.informTime = time
        self.children = set()
        
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = [Node(x,informTime[x]) for x in range(n)]
        for i,v in enumerate(manager):
            if v == -1:continue
            nodes[v].children.add(nodes[i])        
            
        def recursive(node):
            if not node:return 0
            temp = 0
            for n in node.children:
                temp = max(temp,recursive(n))
            return temp+node.informTime
        
        return recursive(nodes[headID])
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        reports = collections.defaultdict(list)
        for i, m in enumerate(manager):
            reports[m].append(i)
        
        def dfs(i):
            return informTime[i] + max([dfs(r) for r in reports[i]], default=0) 
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        inputs = {i:0 for i in range(n)}
        graph = {i: set() for i in range(n)}
        for i, m in enumerate(manager):
            # edge m --> i
            if m == -1: continue
            if i not in graph[m]:
                graph[m].add(i)
                inputs[i] += 1
                
        stack = [(headID, 0)]
        ans = 0
        while stack:
            i, elapsed = stack.pop()
            ans = max(ans, elapsed)
            # find all subordinates of i
            new_elapsed = elapsed + informTime[i]
            for nb in graph[i]: 
                inputs[nb] -= 1
                if inputs[nb] == 0:
                    stack.append((nb, new_elapsed))
                    
        return ans
                    
                


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i]!=-1:
                informTime[i]+=dfs(manager[i])
                manager[i]=-1
            return informTime[i]
        return max(map(dfs,range(n)))          

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        time = [-1 for _ in range(n)]
        time[headID] = 0
        result = 0
        for i in range(n):
            index = i
            path = []
            while time[index] == -1:
                path.append(index)
                index = manager[index]
            for employee in reversed(path):
                #print(\"employee: {}, manager: {}, time of manager: {}, informTime of manager: {}\".format(employee, manager[employee],  time[manager[employee]], informTime[manager[employee]]))
                time[employee] = time[manager[employee]] + informTime[manager[employee]]
            result = max(result, time[i])
        print(time)
        return result            
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = {}
        for i,man in enumerate(manager):
            if man == -1:
                continue
            if man not in subs:
                subs[man] = set()
            subs[man].add(i)
            
        queue = [(headID, 0)]
        maxInformTime = 0
        
        while queue:
            curr,informedAt = queue.pop()
            if curr not in subs:
                continue
                
            currInformTime = informTime[curr] + informedAt
            maxInformTime = max(maxInformTime, currInformTime)
            emps = subs[curr]  
            for e in emps:
                queue.append((e,currInformTime))
                
        return maxInformTime


class RelationTree:
    def __init__(self, e_id, time):
        self.e_id = e_id
        self.time = time
        self.subs = []
        

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        relation_dict = collections.defaultdict(list)
        for i, m_id in enumerate(manager):
            relation_dict[m_id].append(i)
        self.max_time = 0
        def createTree(e_id, cum_time):
            curr_root = RelationTree(e_id, informTime[e_id])
            if curr_root.time:
                for sub_id in relation_dict[e_id]:
                    curr_root.subs.append(createTree(sub_id, cum_time + curr_root.time))
            else:
                self.max_time = max(self.max_time, cum_time)
            return curr_root
        root = createTree(headID, 0)
        
        return self.max_time
        
        


class Node:
    def __init__(self, id, informTime=0):
        self.id = id
        self.employees = []
        self.informTime = informTime

class Solution:
    def construct_tree(self, headID, managers, informTime):
        manager_to_employees = {}
        for employee, manager in enumerate(managers):
            if manager in manager_to_employees:
                manager_to_employees[manager].append(employee)
            else:
                manager_to_employees[manager] = [employee]
        
        root = Node(headID, informTime[headID])
        stack = [root]
        while stack:
            node = stack.pop()
            if node.id not in manager_to_employees:
                continue
            for employee in manager_to_employees[node.id]:
                next_node = Node(employee, informTime[employee])
                node.employees.append(next_node)
                stack.append(next_node)
        return root

    def shortest_informTime(self, root): 
        max_time = 0
        if root and root.employees:
            for employee in root.employees:
                max_time= max(max_time, self.shortest_informTime(employee))
            max_time += root.informTime
        return max_time

    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        root = self.construct_tree(headID, manager, informTime)
        return self.shortest_informTime(root)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        #DFS
        
        subordinates = collections.defaultdict(list)
        
        for i, m in enumerate(manager):
            
            if i != headID:
                subordinates.setdefault(m,[]).append(i)
                #subordinates[m].append(i)
                
        self.res = 0
        
        
        def dfs(manager, time):
            
            self.res = max(self.res, time)
            
            for subordinate in subordinates[manager]:
                
                dfs(subordinate, time + informTime[manager])
                
        dfs(headID, 0) 
        
        return self.res


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinates = collections.defaultdict(list)
        for i in range(n):
            subordinates[manager[i]].append(i)
    
        queue = collections.deque([(headID, 0)])
        max_time = 0
        while queue:
            employee_mgr, time = queue.popleft()
            max_time = max(max_time, time)
            queue.extend((employee, time + informTime[employee_mgr]) for employee in subordinates[employee_mgr])
        
        return max_time

class Solution:
    ans = 0
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # Time Limit Exceeded
        d = {}
        totalTime = [-1]*n
        def help(index):
            if index == headID:
                d[index] = 0
                return 0
            else:
                m = manager[index]
                cost = 0
                if m in d:
                    cost = informTime[m] + d[m]
                else:
                    cost = informTime[m] + help(m)
                d[index]=cost
                totalTime[index] = cost
                self.ans = max(self.ans,cost)
                return cost
        for i in range(n):
            if totalTime[i] <0:
                help(i)
        return self.ans
        


class Node:
    def __init__(self, time):
        self.time = time
        self.children = []

def dfs(node):
    res = node.time
    if node.children:
        res += max(dfs(c) for c in node.children)
    return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = [Node(t) for t in informTime]
        for i in range(n):
            if i == headID:
                continue
            nodes[manager[i]].children.append(nodes[i])
        return dfs(nodes[headID])

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        
        
        # my solution ... 1744 ms ... 48 % ... 68.7 MB ... 0 %
        #  time: O(n)
        # space: O(n)
        
        def func(parent, t):
            self.res = max(self.res, t)
            for child in subs[parent]:
                func(child, t + informTime[parent])
        
        subs = collections.defaultdict(set)
        for i,m in enumerate(manager):
            if m != -1:
                subs[m].add(i)
        self.res = 0
        func(headID, 0)
        return self.res
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        total_time = [0] * n
        total_time[headID] = informTime[headID]
        for i in range(n):
            if total_time[i] == 0:
                path = [i]
                c_id = manager[i]
                while c_id != -1 and total_time[c_id] == 0:
                    path.append(c_id)
                    c_id = manager[c_id]
                c_time = total_time[c_id]
                if len(path) > 0:
                    total_time[path[-1]] = informTime[path[-1]] + c_time
                    for j in range(len(path)-2, -1, -1):
                        total_time[path[j]] = informTime[path[j]] + total_time[path[j+1]]
        return max(total_time)
                    


class TreeNode:
    def __init__(self, val, children):
        self.val = val
        self.children = children

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        people = []
        for time in informTime:
            people.append(TreeNode(time, []))
        for ID, man in enumerate(manager):
            if man != -1:
                people[man].children.append(people[ID])
        def dfs(node):
            return node.val + max(dfs(child) for child in node.children) if node.children else 0
        return dfs(people[headID])
        


class Solution:
    def dfs(self,headId,employee,informTime):
        maxTime = 0
        
        for e in employee[headId]:
            maxTime = max(maxTime,self.dfs(e,employee,informTime) + informTime[headId])
            
        return maxTime
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        employee = [[0 for i in range(0)] for j in range(n)]
        
        for i in range(n):
            if manager[i] != -1:
                employee[manager[i]].append(i)
            
        return self.dfs(headID,employee,informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = {}
        for i,man in enumerate(manager):
            if man == -1:
                continue
            if man not in subs:
                subs[man] = set()
            subs[man].add(i)
            
        queue = [(headID, 0)]
        maxInformTime = 0
        
        while queue:
            curr,informedAt = queue.pop()
            if curr not in subs:
                continue
                
            emps = subs[curr]  
            for e in emps:
                currInformTime = informTime[curr] + informedAt
                maxInformTime = max(maxInformTime, currInformTime)
                queue.append((e,currInformTime))
                
        return maxInformTime


from collections import deque


class Node:
    def __init__(self, id: int, inform_t: int):
        self.id = id
        self.children = []
        self.inform_t = inform_t
    
    def __repr__(self):
        return f'<{self.id} ({self.inform_t}): {len(self.children)}>'
    
    def total_inform_time(self):
        t = self.inform_t
        if self.children:
            t += max(ch.total_inform_time() for ch in self.children)
        return t

class Solution:
    
    def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:
        nodes = [None] * len(manager)
        root = None
        for id, man_id in enumerate(manager):
            if nodes[id] is None:
                nodes[id] = Node(id, inform_time[id])
            
            if man_id >= 0:
                if nodes[man_id] is None:
                    nodes[man_id] = Node(man_id, inform_time[man_id])

                nodes[man_id].children.append(nodes[id])
            else:
                root = nodes[id]
        return root
    
    
    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:
        root = self.build_tree(manager, inform_time)
        return root.total_inform_time()


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        #Step1: build the graph
        adjList = collections.defaultdict(list)
        for i, (u, v) in enumerate(zip(manager, informTime)):
            adjList[u].append((i, v))
        #Step2: dfs with stack
        stack = adjList[-1]
        res = 0
        while stack:
            u, v = stack.pop()
            res = max(res, v)
            for nu, nv in adjList[u]:
                stack.append((nu, v + nv))
        return res
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        employee_to_manager = collections.defaultdict(list)
        
        for i in range(len(manager)):
            employee_to_manager[manager[i]].append(i)
        queue = collections.deque()
        queue.append((headID, informTime[headID]))
        
        total_time = 0
        
        while queue:
            manager, t = queue.popleft()
            
            total_time = max(total_time, t)
            
            for employee in employee_to_manager[manager]:
                queue.append((employee, t +  informTime[employee]))
        return total_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        if n == 1:
            return 0 

        graph = defaultdict(list)

        for idx, manager in enumerate(manager):
            graph[manager].append((informTime[manager], idx))
        

        pQueue = [(0, headID)]
        maxTime = 0 

        while pQueue:
            
            currTime , currId = heapq.heappop(pQueue)
            maxTime = max(maxTime, currTime)
            
            for nextTime, nei in graph[currId]:
                heapq.heappush(pQueue, (currTime + nextTime, nei))

        return maxTime

from collections import defaultdict
class Solution:
    # time for a manager = time[employee] + time[manager]
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # [manager1, manager2...]
        # 0th employee, 1st employee
        mp = defaultdict(list) # {manager: [employee id]}
        for i in range(n):
            if manager[i] != -1:
                mp[manager[i]].append(i)
        
        def find_time(manager):
            employees = mp[manager]
            maxval = 0
            for employee in employees:
                maxval = max(maxval, find_time(employee))
            return maxval + informTime[manager]
        
        return find_time(headID)
            
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        q = [[headID, informTime[headID]]]
        d = defaultdict(list)
        for i, val in enumerate(manager):
            d[val].append(i)
        res = 0
        while True:
            new_q = []
            cur_max_time = 0
            while q:
                index, time = q.pop()
                res = max(res, time)
                for v in d[index]:
                    new_q.append((v, time+informTime[v]))
            q = new_q[:]
            
            if not q:
                break
        return res

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        '''
        
        if not manager:
            return 0
        
        #building the graph
        graph = defaultdict(list)
        for v in range(n):
            graph[manager[v]].append(v)
        
        #For each node, we have to take the hieghest time
        #returned from its subordinates/children
        def dfs(node):
            if node not in graph:
                return informTime[node]
            else:
                return  informTime[node]+max(map(lambda n: dfs(n), graph[node]))
        
        return dfs(headID)
        '''
        
        if not manager: return 0
        g = collections.defaultdict(list)
        for e, m in enumerate(manager):
            g[m].append(e)
        
        def dfs(u):
            if u not in g: return 0
            return informTime[u]+max(dfs(v) for v in g[u])
        
        return dfs(headID)
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        pass
        
        
        
        def helper(i):
            if i not in g:
                return 0
            
            children = g[i]
            nchild = len(children)
            res = 0
            for j in range(nchild):
                v = children[j]
                res = max(res,helper(v))
            return res + informTime[i]
                
                
        
        g = {}
        
        n = len(manager)
        for i in range(n):
            themanager = manager[i]
            if themanager == -1:
                continue
            if themanager not in g:
                g[themanager] = []
                
            g[themanager].append(i)
            
        return helper(headID)


class Solution:
    def numMin(self, n: int, headID: int, subordinates: List[int], informTime: List[int]) -> int:
        if subordinates[headID] == []:
            return 0
        else:
            return informTime[headID] + max(self.numMin(n, e, subordinates, informTime) for e in subordinates[headID])
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinates = [[] for x in range(n)]
        for i, m in enumerate(manager):
            if m != -1:
                subordinates[m].append(i)
        print(subordinates)
        return self.numMin(n, headID, subordinates, informTime)


import heapq

class Solution:
    def numOfMinutes(self, N: int, H: int, M: List[int], T: List[int]) -> int:
        graph = defaultdict(lambda:[])
        for i, m in enumerate(M):
            if i != H:
                graph[m].append(i)

        cnt = 0; heap = []
        heapq.heappush(heap, (T[H], H))
        while heap:
            cur = heapq.heappop(heap)
            cnt += 1
            if cnt == N:
                return cur[0]
            if cur[1] in graph:
                for sub in graph[cur[1]]:
                    heapq.heappush(heap, (T[sub]+cur[0], sub))



class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        man_idx = [[man, idx] for idx, man in enumerate(manager)]
        man_copy = [[man, idx] for idx, man in enumerate(manager)]
        max_time = 0
        curr_time = 0
        memo_table = {}
        start = man_idx[-1][1]
        while man_idx:
            curr_man = man_idx.pop()
            if curr_man[1] in memo_table:
                curr_time += memo_table[curr_man[1]]
                memo_table[start] = curr_time
                max_time = max(max_time, curr_time)
                if len(man_idx) > 0:
                    start = man_idx[-1][1]
                curr_time = 0
                continue
            curr_time += informTime[curr_man[1]]
            if curr_man[0] == -1:
                max_time = max(max_time, curr_time)
                memo_table[start] = curr_time
                if len(man_idx) > 0:
                    start = man_idx[-1][1]
                curr_time = 0
            else:
                man_idx.append(man_copy[curr_man[0]])
        return max_time


import sys

sys.setrecursionlimit(10**6) 

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.par = None
        self.kids = []

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        nodes = [TreeNode(informTime[emp]) for emp in range(n)]
        for emp in range(n):
            if manager[emp] != -1:
                nodes[emp].par = nodes[manager[emp]]
                nodes[manager[emp]].kids.append(nodes[emp])
        
        head = nodes[headID]
        
        def helper(node):
            return node.val + max([helper(k) for k in node.kids],default=0)
        
        return helper(head)

from typing import List


class TreeNode(object):
    def __init__(self, val: int):
        self.val = val
        self.children = []


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # construct tree
        tree_map = {headID: TreeNode(headID)}
        for i in range(n):
            if i == headID:
                continue
            if i not in tree_map:
                tree_map[i] = TreeNode(i)
            if manager[i] not in tree_map:
                tree_map[manager[i]] = TreeNode(manager[i])
            tree_map[manager[i]].children.append(i)

        # level order
        res = 0
        root = tree_map[headID]
        queue = [(root, 0)]
        while len(queue) > 0:
            r, s = queue.pop(0)
            if len(r.children) == 0:
                res = max(res, s)
            for c in r.children:
                queue.append((tree_map[c], s + informTime[r.val]))
        return res

import collections
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(len(manager)):
            if manager[i] != -1:
                graph[manager[i]].append(i)
        queue = [(headID, 0)]
        ans = 0
        while queue:
            m, val = queue.pop(0)
            ans = max(ans, val)
            for w in graph[m]:
                queue.append((w, val+informTime[m]))
        return ans
                        


class Solution: 

    def processEmployee(self, employee, managerOfEmployee, informTime, dp):
        if employee == -1 or dp[employee]: return employee
        dp[employee] = 1
        managerOfEmployee[employee] = self.processEmployee(managerOfEmployee[employee], managerOfEmployee, informTime, dp)
        if managerOfEmployee[employee] != -1: informTime[employee] += informTime[managerOfEmployee[employee]]
        return employee
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        dp = [0] * (n + 1)
        for employee in range(n): self.processEmployee(employee, manager, informTime, dp)                          
        return max(informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i,t):
            if i not in dic: self.ans = max(self.ans,t)
            for a,b in dic[i]:
                dfs(a,t+b)
        dic,self.ans = defaultdict(list),0
        for i,m in enumerate(manager): dic[m].append((i,informTime[i]))
        dfs(dic[-1][0][0],dic[-1][0][1])
        return self.ans
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subord = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0:
                subord[m].append(i)
                
        return self.dfs(headID, subord, informTime)
        
    def dfs(self, i, subord, informTime):
        return max([self.dfs(e, subord, informTime) for e in subord[i]] or [0]) + informTime[i]

class Solution:
    def numMin(self, total_time, n: int, headID: int, subordinates: List[int], informTime: List[int]) -> int:
        if subordinates[headID] == []:
            return total_time
        else:
            return max(self.numMin(informTime[headID] + total_time, n, e, subordinates, informTime) for e in subordinates[headID])
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinates = [[] for x in range(n)]
        for i, m in enumerate(manager):
            if m != -1:
                subordinates[m].append(i)
        print(subordinates)
        return self.numMin(0, n, headID, subordinates, informTime)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        manager2employee = defaultdict(list)
        for employee, manager in enumerate(manager):
            manager2employee[manager].append(employee)
        @lru_cache(None)
        def dfs(manager):
            if not manager2employee[manager]:
                return 0
            return max([informTime[manager] + dfs(e) for e in manager2employee[manager]])
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        graph= defaultdict(list)
        for child, parent in enumerate(manager):
            
            graph[parent].append(child)
        q= deque([(headID, informTime[headID])])
        maxval=0
        while q:
            head, time= q.popleft()
            maxval= max(maxval,time)
            for child in graph[head]:
                q.append((child, time+ informTime[child]))
        return maxval
        
        
    
            
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(list(map(dfs, list(range(len(manager))))))
        
            


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        max_time = 0
        node_stack = []
        for node in manager:
            time = 0
            while node != -1:
                node_stack.append(node)
                node = manager[node]
            while node_stack:
                node = node_stack.pop()
                time += informTime[node]
                informTime[node] = time
                manager[node] = -1
                if time > max_time:
                    max_time = time
        return max_time

class Solution:
    class Node:
        def __init__(self, id):
            self.id = id
            self.next = []
            
            
    # BFS on a generated tree => O(n)
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if len(manager) == 0: return 0

        directs = defaultdict(list)
        for i, m in enumerate(manager):
            directs[manager[i]].append(i)
        # print(directs)
        q = [(headID, 0)]
        t = 0
        while len(q) > 0:
            (curr, currT) = q.pop(0)
            t = max(t, currT)
            if curr in directs:
                for d in directs[curr]:
                    q.append((d, currT + informTime[curr]))
        return t


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        # create graph
        # depth first search on the tree
        # sum the maximum time it takes to inform each level
        
        relationships = {}
        
        for i in range(len(manager)):
            if not manager[i] in relationships:
                relationships[manager[i]] = [[],0]
            relationships[manager[i]][0].append(i)
            
            if not i in relationships:
                relationships[i] = [[],0]
            relationships[i][1] = informTime[i]
        
        
        def dfs(node, graph):
            if not graph[node][0]: # leaf
                return 0
            else:
                maxTime = 0
                informTime = graph[node][1]
                
                for nbr in graph[node][0]:
                    maxTime = max(maxTime, dfs(nbr, graph) + informTime)
                
                return maxTime
        
        return dfs(headID, relationships)
                    
            
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)

            
            
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # adjacency list
        
        adj = [[] for _ in range(n)]
        s = headID
        ans = 0
        visited = [False] * n
        
        for i in range(n):
            if manager[i] == -1:
                continue
            adj[manager[i]].append(i)
            
        def dfs(s, time):
            nonlocal ans
            Leaf = True
            
            for i in adj[s]:
                if not visited[i]:
                    Leaf = False
                    visited[i] = True
                    dfs(i, time + informTime[i])
                    
            if Leaf:
                ans = max(ans, time)
            
            
        dfs(s, informTime[s])
        
        return ans


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = {}
        for i,man in enumerate(manager):
            if man == -1:
                continue
            if man not in subs:
                subs[man] = set()# if man != -1 else None
            subs[man].add(i)
            
        #print(subs)
        queue = [(headID, 0, 0)]
        informTimes = {}
        
        while queue:
            curr, level, informedAt = queue.pop()
            if curr not in subs:
                continue
            emps = subs[curr]
                            
            for e in emps:
                if level not in informTimes:
                    informTimes[level] = []
                currInformTime = informTime[curr] + informedAt
                informTimes[level].append(currInformTime)
                queue.append((e, level+1, currInformTime))
        if not informTimes:
            return 0
        
        maxInformTime = -1
        for level, informTimesLevel in list(informTimes.items()):
            maxInformTime = max(maxInformTime, max(informTimesLevel))
        #maxLevel = max(informTimes.keys())
        return maxInformTime


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 1:
            return informTime[0]
        graph = defaultdict(list)
        
        for i, m in enumerate(manager):
            if m == -1:
                continue
            graph[m].append(i)
        
        #print( graph )
        totalTime = []
        def dfs( node, time=0):
            nonlocal totalTime
            if not graph[node]:
                totalTime.append(time)
            for e in graph[node]:
                dfs(e, time+informTime[e])
            
        
        dfs(headID, time=informTime[headID])
        #print(totalTime)
        return max(totalTime)

class Employee:
    def __init__(self, idx, inf_time):
        self.idx = idx
        self.inf_time = inf_time
        self.subs = []

class Solution:            
    def numOfMinutesCoool(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(map(dfs, manager))
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs_dct = defaultdict(list)
        for empl, manager in enumerate(manager):
            subs_dct[manager].append(empl)
        
        root = Employee(headID, informTime[headID])
        def makeTree(node):
            for sub in subs_dct[node.idx]:
                node.subs.append(Employee(
                    sub,
                    node.inf_time + informTime[sub]
                ))
            for sub_node in node.subs:
                makeTree(sub_node)
        makeTree(root)
        
        total = 0
        def dfs(node):
            if not node.subs:
                return node.inf_time
            return max([dfs(sub_node) for sub_node in node.subs])
        
        return dfs(root)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 0:
            return 0
        
        maxx = 0
        cache = {}
        for i in range(n):
            curr = i
            count = 0
            while curr != headID:
                curr = manager[curr]
                count += informTime[curr]
                if curr in cache:
                    count += cache[curr]
                    break
            
            # print(i, count)
            cache[i] = count
            # print(cache)
            maxx = max(maxx, count)
        return maxx

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:
        graph = defaultdict(list)
        for subord, manager in enumerate(managers):
            graph[manager].append(subord)
        
        return self.dfs(headID, graph, informTime)
    
    def dfs(self, node, graph, informTime):
        longest = 0
        for child in graph[node]:
            longest = max(longest, self.dfs(child, graph, informTime))
        return longest + informTime[node]
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
                      
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
                      
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
                      
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:
        # if I want to go from top-to-bottom I will always have to search for the employees of a given manager via linear search
        # -> not efficient, if I do that I explicitly build up a graph or adjacency matrix (manager -> employees)
        # -> O(n) time + O(n) space
        
        # can I go bottom-up too to avoid the space cost? -> I think would work if I can from all employees with time 0 (else too expensive)
        manager_to_employees = [[] for _ in managers]
        for employee, manager in enumerate(managers):
            if manager == -1: continue
            manager_to_employees[manager].append(employee)
        max_time = [0]
        self.dfs(headID, informTime, manager_to_employees, 0, max_time)
        return max_time[0]
        
    def dfs(self, ID, informTime, manager_to_employees, curr_time, max_time):
        if not manager_to_employees[ID]: 
            max_time[0] = max(max_time[0], curr_time)
        for employee in manager_to_employees[ID]:
            self.dfs(employee, informTime, manager_to_employees, curr_time + informTime[ID], max_time)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        

        reports = collections.defaultdict(set)
        
        for i, m in enumerate(manager):
            if m == -1:
                managerId = i
            else:
                reports[m].add(i)
            
        queue = collections.deque([(managerId, 0)])
        maxT = 0
        visited = set()
        while queue:
            person, time = queue.popleft()
            if person in visited:
                continue
                
            maxT = max(time, maxT)
            
            for r in reports[person]:
                queue.append((r, time + informTime[person]))
                
    
        return maxT
            


class Employee:
    def __init__(self, employeeID, informTime):
        self.id = employeeID
        self.informTime = informTime 
        self.sub = []
    
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 1:
            return informTime[0]
        
        head = self.buildEmpTree(n, manager, headID, informTime)
        
        return self.maxTime(head)
        
    def buildEmpTree(self, n, manager, headID, informTime):
        s = {}
        for i in range(n):
            s[i] = Employee(i, informTime[i])
            
        for i in range(n):
            if manager[i] == -1:
                continue
            s[manager[i]].sub.append(s[i])
                    
        return s[headID]
        
    def maxTime(self, root):
        if not root.sub:
            return root.informTime
        
        curMax = root.informTime
        
        for subordinate in root.sub:
            curMax = max(curMax, root.informTime + self.maxTime(subordinate))
        
        return curMax


class Solution:
    def get_managers_delay(self, index: int, cache: List[int], manager: List[int], informTime: List[int]) -> int:        
        if manager[index] == -1:
            return informTime[index]
        
        if cache[index] != -1:
            return cache[index]
        
        managers_delay = self.get_managers_delay(manager[index], cache, manager, informTime)
        cache[index] = managers_delay + informTime[index]
        
        return cache[index]
    
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        cache = [-1] * n
        max_inform_time = 0
        
        for i in range(n):
            inform_time = self.get_managers_delay(i, cache, manager, informTime)
            max_inform_time = max(max_inform_time, inform_time)
            
        return max_inform_time

class Employee:
    def __init__(self, idx, inf_time):
        self.idx = idx
        self.inf_time = inf_time
        self.subs = []

class Solution:            
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs_dct = defaultdict(list)
        for empl, manager in enumerate(manager):
            subs_dct[manager].append(empl)
        
        root = Employee(headID, informTime[headID])
        def makeTree(node):
            for sub in subs_dct[node.idx]:
                node.subs.append(Employee(
                    sub,
                    node.inf_time + informTime[sub]
                ))
            for sub_node in node.subs:
                makeTree(sub_node)
        makeTree(root)
        
        total = 0
        def dfs(node):
            if not node.subs:
                return node.inf_time
            return max([dfs(sub_node) for sub_node in node.subs])
        
        return dfs(root)

from collections import defaultdict, deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if not n:
            return 0
        edges = defaultdict(list)
        root = 0
        for idx, val in enumerate(manager):
            if val == -1:
                root = idx
            else:
                edges[val].append(idx)
        self.ans = 0
        self.dfs(root, edges, informTime[root], informTime)
        return self.ans
    
    def dfs(self, node, edges, curr_time, informTime):
        self.ans = max(self.ans, curr_time)
        for reporter in edges[node]:
            self.dfs(reporter, edges, curr_time+informTime[reporter], informTime)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordinate = collections.defaultdict(list)
        for i in range(n):
            subordinate[manager[i]].append(i)
        def solve(ID):
            if subordinate[ID]:
                return max(solve(i) for i in subordinate[ID]) + informTime[ID]
            else:
                return 0
        return solve(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = defaultdict(list)
        for index, managerId in enumerate(manager):
            graph[managerId].append(index)
        result = 0
        def dfs(node, currentTime):
            nonlocal graph, result
            if node not in graph:
                result = max(result, currentTime)
                return
            for emp in graph[node]:
                dfs(emp, currentTime + informTime[node])
        dfs(headID, 0)
        return result

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # the employees are on a tree
        # each time we go down one level, we wait X minutes
        # the answer is the max among all leaf nodes (employees that don't manage)
        
        # first: creats aux data structures to support a tree-like interaction
        # given an employee: know it's children
        # build a map: key: employeeID -> List of children IDs
        
        # traverse the tree in BFS manner
        # once a leaf is found, update the solution
        
        tree = {}
        for i in range(len(manager)):
            if manager[i] in tree:
                tree[manager[i]].append(i)
            else:
                tree[manager[i]] = [i]
        
      
        queue = [(headID, informTime[headID])]
        solution = -1
        while queue:
            node, time = queue.pop(0)    
            solution = max(solution, time)
            
            if node in tree:
                for n in tree[node]:
                    queue.append((n, time + informTime[n]))
            
        
        return solution

from collections import deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        adjList = {} 
        adjList[headID] = [] 
        for index, emp in enumerate(manager):
            if emp == -1:
                continue 
            if emp not in adjList: 
                adjList[emp] = []
            adjList[emp].append(index)
        
        queue = deque()        
        queue.append((headID, 0))

        maxMinutes = float('-inf')
        while queue:
            for i in range(len(queue)):
                idx, time = queue.popleft() 
                if informTime[idx] == 0:
                    maxMinutes = max(maxMinutes, time)
                else: 
                    for sub in adjList[idx]:
                        queue.append((sub, time+informTime[idx]))
                        
        return maxMinutes 

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n == 0:
            return 0
        if n == 1:
            return informTime[0]
        dic = collections.defaultdict(list)
        for i, x in enumerate(manager):
            if x != -1:
                dic[x].append(i)
        def dfs(node):
            time = 0
            if not dic[node]:
                return 0
            for sub in dic[node]:
                time = max(time, informTime[node] + dfs(sub))
            return time
        return dfs(headID)
                
                


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        graph = {i:[] for i in range(n)}
        for child, parent in enumerate(manager):
            if parent == -1: continue
            graph[parent].append(child)
        
        time = 0
        pq = [(0,headID)]
        maxtime = 0
        while pq:
            curtime, curm = heapq.heappop(pq)
            for nxt in graph[curm]:
                heapq.heappush(pq, (curtime+informTime[curm], nxt))
            maxtime = curtime
        return maxtime
            
                    


from collections import defaultdict
class Solution:
    def __init__(self):
        self.ans=0
    
    def helper(self, curr, children, timesofar):
        if not children:
            self.ans=max(self.ans, timesofar)
        for i in children:
            self.helper(i, self.graph[i], timesofar+self.informTime[i])
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        self.informTime=informTime
        self.graph=defaultdict(list)
        for idx,i in enumerate(manager):
            self.graph[i].append(idx)
        self.helper(headID, self.graph[headID], self.informTime[headID])
        return self.ans

class Solution:
    class Node:
        def __init__(self, id):
            self.id = id
            self.next = []
            
            
    # BFS on a generated tree => O(n)
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if len(manager) == 0: return 0

        directs = defaultdict(list)
        for i, m in enumerate(manager):
            directs[manager[i]].append(i)

        q = deque([(headID, 0)])
        t = 0
        while len(q) > 0:
            (curr, currT) = q.popleft()
            t = max(t, currT)
            if curr in directs:
                for d in directs[curr]:
                    q.append((d, currT + informTime[curr]))
        return t


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        q = collections.deque([(headID, 0)])
        subordinates = collections.defaultdict(list)
        res = 0
        for i, v in enumerate(manager):
            subordinates[v].append(i)
            
        while q:
            u, time = q.popleft()
            res = max(res, time)
            for v in subordinates[u]:
                q.append((v, time + informTime[u]))
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        total_time, company_dict = 0, {}
        for i, m in enumerate(manager): # ix, emp
            if m not in company_dict:
                company_dict[m] = set([i]) # unique ix
            else:
                company_dict[m].add(i) # in dict {ix:ID ...}
        
        def get_emp_inf_time(manager, time):
            nonlocal total_time
            if manager not in company_dict: # new => {M:t ...}
                total_time = max(total_time, time)
                return
            for e in company_dict[manager]: 
                time_to_inform = time + informTime[manager] # [1] mng : emp with time
                get_emp_inf_time(e, time_to_inform) # rec. [2] emp time     
        head = list(company_dict[-1])[0] # add the head
        get_emp_inf_time(head, 0) # rec. [3]: add the last
        return total_time

import collections
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(len(manager)):
            if manager[i] != -1:
                graph[manager[i]].append(i)
        queue = [(headID, 0)]
        ans = 0
        while queue:
            temp = []
            maxx = 0
            for m, val in queue:
                ans = max(ans, val)
                for w in graph[m]:
                    temp.append((w, val+informTime[m]))
            queue = temp
        return ans
                        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        q = [(headID, 0)]
        subordinates = collections.defaultdict(list)
        res = 0
        
        for i, v in enumerate(manager):
            subordinates[v].append(i)
            
        while q:
            u, time = q.pop(0)
            res = max(res, time)
            for v in subordinates[u]:
                q.append((v, time + informTime[u]))
        return res
    
    # https://leetcode.com/problems/time-needed-to-inform-all-employees/discuss/532530/Python3-Easy-Python-Solution%3A-DijkstraBFSDFS


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1:
            return 0
        sub = collections.defaultdict(list)
        for i in range(len(manager)):
            sub[manager[i]].append(i)
            
        total = 0
        q = collections.deque([(headID, 0)]) #id, time
        while q:
            employee, time = q.popleft()
            if not sub[employee]:
                total = max(total, time)
            for nxt in sub[employee]:
                q.append((nxt, time+informTime[employee]))
        return total

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        from collections import defaultdict
        
        res = 0
        children = defaultdict(list)
        
        for i, e in enumerate(manager):
            children[e].append(i)
        queue = collections.deque([(headID, informTime[headID])])
        
        while queue:
            employeeID, time_needed = queue.popleft()
            res = max(res, time_needed)
            
            for child in children[employeeID]:
                queue.append((child, time_needed+informTime[child]))
        
        return res

import collections
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        d = collections.defaultdict(list)
        for i,k in enumerate(manager):
            if i == headID:
                continue
            
            d[k].append(i)
        
        q = [(0,headID)]
        total = 0
        while q :
            time,node = q.pop(0)
            for i in d[node]:
                q.append((time+informTime[node],i))
                total = max(total,time+informTime[node])
        return total

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        queue = collections.deque([(headID, 0)])
        subordinates = collections.defaultdict(list)
        
        for subordinate,supervisor in enumerate(manager):
            subordinates[supervisor].append(subordinate)

        time = 0
        
        while queue:
            supervisor,currentInformTime = queue.popleft()
            time = max(time,currentInformTime) # We are grabbing the maximum time over here 
            # because the boss might be connected to multiple subord. So whenever time is incremented we add it only once because in the queue we can have multiple subordinates from same boss with same times, so we wanna add it only once 
            
            for subordinate in subordinates[supervisor]:
                queue.append((subordinate,currentInformTime+informTime[supervisor]))
        
        return time   
    
# An alternate to line 13 would be to do xs.append(currentTime) and then on line 19 return max(xs)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        G = collections.defaultdict(list)
        for i,v in enumerate(manager):
            G[v].append(i)
        
        ans = 0
        
        qu = [(G[-1][0], 0)]
        while qu:
            n, v = qu.pop()
            ans = max(ans,v)
            for e in G[n]:
                qu.append((e, v+informTime[n]))
        return ans

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        cache = [-1] * n
        def dfs(cur):
            if cur == -1: return 0
            if cache[cur] == -1:
                cache[cur] = dfs(manager[cur]) + informTime[cur]
            return cache[cur]
        return max([dfs(i) for i in range(n)])

    def numOfMinutes_5pct(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
            res = 0
            for ii in range(len(manager)):
                if informTime[ii]==0:
                    temp = 0
                    index = ii
                    while index!=-1:
                        temp += informTime[index]
                        index = manager[index]
                    res = max(res, temp)
            return res

            
    def numOfMinutes_dfs_wrong(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        time = 0
        ht = {}
        for ii in range(len(manager)):
            #if informTime[ii]==0: ## no sub
            #    continue
            if manager[ii]==-1: ##head
                time = informTime[ii]
                continue
            if manager[ii] not in ht:
                ht[manager[ii]] = {}
                ht[manager[ii]]['subord'] = []
                ht[manager[ii]]['time'] = informTime[ii]
            ht[manager[ii]]['subord'].append(ii)
        print(ht)
            
        queue = collections.deque() ##store managers only
        queue.append(headID)
        #print(queue)
        informed = 1
        while len(queue):
            n_sub = len(queue)
            #print('#########')
            #print(n_sub)
            for ii in range(n_sub):
                m = queue.popleft()
                #print('---------')
                #print(m)
                
                #print(ht[m])
                #if ii == 0:
                #    time += ht[m]['time'] ##same time/parallel
                if m in ht:
                    for e in ht[m]['subord']:
                        if e in ht: ##also a manager
                            queue.append(e)
                #print('after updating queue')
                #print(queue)
                #informed += 1
        return time
                
                


from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:
        managerEmployeeTree = defaultdict(list)
        for i, manager in enumerate(managers):
            managerEmployeeTree[manager].append(i)
        return self._traversal(managerEmployeeTree, headID, informTime)
            
    def _traversal(self, managerEmployeeTree, manager, informTime):
        if managerEmployeeTree.get(manager):
            maxInformTime = 0
            for employee in managerEmployeeTree[manager]:
                employeeInformTime = self._traversal(managerEmployeeTree, employee, informTime)
                maxInformTime = max(maxInformTime, employeeInformTime)
            return informTime[manager] + maxInformTime
        return 0

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        dic = defaultdict(list)
        for em,ma in enumerate(manager):
            dic[ma].append(em)
        
        queue = deque([(headID,0)])
        res = 0
        while queue:
            for _ in range(len(queue)):
                ma,needed_time = queue.popleft()
                res = max(res, needed_time)
                for sub in dic[ma]:
                    queue.append((sub,needed_time+informTime[ma]))
        return res


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        q = collections.deque([(headID, 0)])
        subordinates = collections.defaultdict(list)
        res = 0
        for i, v in enumerate(manager):
            subordinates[v].append(i)
            
        while q:
            u, time = q.popleft()
            res = max(res, time)
            for v in subordinates[u]:
                q.append((v, time + informTime[u]))
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        times = n * [-1]

        def dfs(v):
            times[v] = informTime[v]
            
            if manager[v] == -1:
                return times[v]
            
            parent = manager[v]
            
            if times[parent] != -1:
                times[v] += times[parent]
                return times[v]
            else:
                times[v] += dfs(parent)
                return times[v]
        
        for i, _emp in enumerate(manager):
            if times[i] == -1:
                dfs(i)
        
        return max(times)
            
        
            
            


from typing import List
from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def build_graph():
            g = defaultdict(list)
            for employee_id in range(n):
                manager_id = manager[employee_id]
                if manager_id == -1:
                    continue
                g[manager_id].append(employee_id)
            return g

        g = build_graph()
        max_time = [0]
        def dfs(total_time, employee_id):
            if employee_id not in g:
                max_time[0] = max(total_time, max_time[0])
                return
            subordinates = g[employee_id]
            for subordinate in subordinates:
                dfs(total_time + informTime[employee_id], subordinate)
        
        dfs(0, headID)
        return max_time[0]

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        # graph[a] = [# a list of A's subordinates]
        # calculate time to reach any single employee at the leaf position 
        graph = collections.defaultdict(list)
        for i, manager in enumerate(manager):
            graph[manager].append(i)
            
        
        # return the max time needed to inform all subs
        def calculateTime(manager):
            
            if manager not in graph:
                return 0 
            
            time = 0 
            for emp in graph[manager]:
                time = max(calculateTime(emp) , time)
                
            return time + informTime[manager]
        
        return calculateTime(headID)
       
         


from collections import defaultdict

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # DFS Stack
        self.max = 0
        directSub = self.makeDirectSub(n,manager)
        self.dfs(headID,directSub,informTime)
        return self.max
        
    # def makeDirectSub(self, n, manager):
    #     d = {employee: [] for employee in range(n)}
    #     for employee in range(len(manager)):
    #         if manager[employee] != -1:
    #             d[manager[employee]].append(employee)
    #     return d
            
    def makeDirectSub(self, n, manager):
        d = defaultdict(list)
        for sub, employee in enumerate(manager):
            d[employee].append(sub)
        return d
        
    def dfs(self, headID, directSub,informTime):
        stk = [(headID,0)]
        while stk:
            employee, time = stk.pop()
            self.max = max(self.max,time)
            # add all subemployees and record the time it took them to get the information
            for subEmp in directSub[employee]:
                stk.append((subEmp,time+informTime[employee]))
        return
        
    
# from collections import deque, defaultdict

# class Solution(object):
#     def numOfMinutes(self, n, headID, manager, informTime):
#         \"\"\"
#         :type n: int
#         :type headID: int
#         :type manager: List[int]
#         :type informTime: List[int]
#         :rtype: int
#         \"\"\"
#         if n <= 1:
#             return 0
#         rst = 0
#         childs = defaultdict(list)
#         for idx, parent in enumerate(manager):
#             childs[parent].append(idx)

#         q = deque([(headID, informTime[headID])])
#         while q:
#             cur_id, cur_time = q.popleft()
#             # calculate max
#             rst = max(rst, cur_time)
#             for child in childs[cur_id]:
#                 q.append((child, cur_time + informTime[child]))
#         return rst


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        from collections import defaultdict
        
        res = 0
        
        children = defaultdict(list)
        
        for i, e in enumerate(manager):
            children[e].append(i)
            
        stack = [(headID, informTime[headID])]
        
        while stack:
            employeeID, time_needed = stack.pop()
            res = max(res, time_needed)
            
            for child in children[employeeID]:
                stack.append((child, time_needed+informTime[child]))
        
        return res

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1:
            return 0
        d = defaultdict(list)
        
        for i in range(len(manager)):
            d[manager[i]].append(i)
        
        self.ans = 0
        
        self.dfs(headID, d, 0, informTime)
        return self.ans
    
    def dfs(self, node, d, totalTime, informTime):
        self.ans = max(self.ans, totalTime)
        
        for sub in d[node]:
            self.dfs(sub, d, totalTime + informTime[node], informTime)
            
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        res = 0
        graph = defaultdict(list)
        for index, parent in enumerate(manager):
            graph[parent].append(index)
        
        queue = deque([(headID, informTime[headID])])
        while queue:
            curId, curTime = queue.popleft()
            res = max(res, curTime)
            for child in graph[curId]:
                queue.append((child, curTime + informTime[child]))
        return res
        
        
        
        
        
        
        
#         rst = 0
#         childs = defaultdict(list)
#         for idx, parent in enumerate(manager):
#             childs[parent].append(idx)

#         q = deque([(headID, informTime[headID])])
#         while q:
#             cur_id, cur_time = q.popleft()
#             # calculate max
#             rst = max(rst, cur_time)
#             for child in childs[cur_id]:
#                 q.append((child, cur_time + informTime[child]))
#         return rst


class Solution:
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        from collections import defaultdict
        graph = defaultdict(list)
        for i, m in enumerate(manager): 
            graph[m].append(i)
                
        to_inform = deque([(headID, informTime[headID])])
        max_t = 0
        while to_inform:
            m, t = to_inform.pop()
            max_t = max(max_t, t)
            for s in graph[m]:
                to_inform.append((s, t + informTime[s]))
            
        return max_t

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        timeNeed = [-1] * n
        
        def get_info_time(m):
            if(timeNeed[m] != -1):
                return timeNeed[m]
            m_dad = manager[m]
            if(m_dad == -1):
                timeNeed[m] = 0
            else:
                timeNeed[m] = get_info_time(m_dad) + informTime[m_dad]
            return timeNeed[m]
        

        for i in range(n):
            get_info_time(i)
        
        return max(timeNeed)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = collections.defaultdict(list)
        for i in range(len(manager)):
            if manager[i] == -1:
                continue
            graph[manager[i]].append(i)
        return self.dfs(headID, graph, informTime)
    
    def dfs(self, head, graph, informTime):
        time = 0
        for employee in graph[head]:
            time = max(time, self.dfs(employee, graph, informTime))
        return informTime[head] + time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        report = collections.defaultdict(list)
        for idx, i in enumerate(manager):
            report[i].append(idx)
        
        queue = [(headID, informTime[headID])]
        maxT = 0
        while queue:
            n, t  = queue.pop(0)
            maxT = max(maxT, t)
            for r in report[n]:
                queue.append((r, t+informTime[r]))
        
        return maxT

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        managerMapping = {}
        maxTime = 0
        def dfs(currentTime, currentEmployee, manangerMapping):
            nonlocal maxTime
            if currentEmployee not in managerMapping:
                maxTime = max(currentTime, maxTime)
            else:
                directs = managerMapping[currentEmployee]
                for direct in directs:
                    dfs(currentTime + informTime[currentEmployee], direct, managerMapping)
                    
        for i in range(len(manager)):
            if manager[i] in managerMapping:
                managerMapping[manager[i]].append(i)
            else:
                managerMapping[manager[i]] = [i]
        dfs(0, headID, managerMapping)
        return maxTime

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if n <= 1:
            return 0
        rst = 0
        childs = defaultdict(list)
        for idx, parent in enumerate(manager):
            childs[parent].append(idx)

        queue = deque([(headID, informTime[headID])])
        while queue:
            cur_id, cur_time = queue.popleft()
            # calculate max
            rst = max(rst, cur_time)
            for child in childs[cur_id]:
                queue.append((child, cur_time + informTime[child]))
        return rst

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        d = collections.defaultdict(list)
        for i in range(n):
            d[ manager[i] ].append(i)
        
        res = 0
        que = collections.deque( [ [ d[-1][0], 0 ] ] )
        
        while que:
            cur, time = que.popleft()
            res = max(res, time)
            time += informTime[cur]
            
            for t in d[cur]:
                que.append( [t, time] )
        
        return res
        


from collections import deque
class Solution:
    
    def max_at_level(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = deque([headID])
        final_time_list = []
        while len(subs) > 0:
            managers_at_level = len(subs)
            level_time_list = []
            for i in range(managers_at_level):
                current_sub = subs.popleft()
                level_time_list.append(informTime[current_sub])
                subs += [index for index, val in enumerate(manager) if val == current_sub ]
            final_time_list.append(level_time_list)
        
        total_time = 0
        for level_list in final_time_list:
            total_time += max(level_list) 
        return total_time
    
    def numOfMinutesRecu(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subs = [index for index, val in enumerate(manager) if val == headID]
        if subs:
            time_sum = []
            for sub in subs:
                time_sum.append(self.numOfMinutes(n, sub, manager, informTime) + informTime[headID])
            return max(time_sum)
        else:
            return informTime[headID]
        
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        stack = [(headID, informTime[headID])]
        res = 0
        
        children = defaultdict(list)
        for i, e in enumerate(manager):
            children[e].append(i)
        
        while stack:
            curr_id, curr_time = stack.pop()
            res = max(res, curr_time)
            #children = [index for index, val in enumerate(manager) if val == curr_id]
            for child in children[curr_id]:
                stack.append((child, curr_time+informTime[child]))
        return res

from collections import defaultdict 
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        if len(manager) <= 1:
            return informTime[headID]
        
        graph = defaultdict(list)
            
        q = deque()
        
        def bfs(graph):
            time_so_far = 0
            while q:
                node, time_taken = q.popleft()
                time_so_far  = max(time_so_far, time_taken)
                for next_node in graph[node]:
                    q.append([next_node, time_taken + informTime[next_node]])
            return time_so_far        
        
        for m in range(len(manager)):
            if manager[m] != -1:
                graph[manager[m]].append(m)
                  
        q.append([headID, informTime[headID]])
        
        return  bfs(graph)
        
        
         


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

        sub = collections.defaultdict(list)
        for i,v in enumerate(manager):
            sub[v].append(i)
        res = -float('inf')
        def dfs(fa,time):
            nonlocal res
            if not sub[fa]: 
                res = max(res,time)
            else:
                for son in sub[fa]:
                    dfs(son,time+informTime[fa])
            return
        dfs(headID,0)
        return res if res < float('inf') else -1


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        if len(manager) == 1:
            return informTime[0]
        
        d=defaultdict(list)
        for i,e in enumerate(manager):
            d[e].append(i)
        #print(d)
        
        '''
        q=[d[-1]]
        mt=1
        time=-1
        while q:
            time+=mt
            mt=0
            print(\"TIme:- \",time,\"  \",\"Queue:- \",q)
            n=len(q)
            for i in range(n):
                x=q.pop(0)
                if type(x) != int:
                    mt = max(mt,informTime[x[0]])
                    for e in d[x[0]]:
                        q.append(e)
                else:
                    mt = max(mt,informTime[x])
                    for e in d[x]:
                        q.append(e)
        return time
        '''
        
        self.time = 0
        def dfs(x,mt):
                
            if type(x)!=int:
                if not d[x[0]]:
                    self.time = max(mt,self.time)
                for e in d[x[0]]:
                    dfs(e,mt+informTime[x[0]])
            else:
                if not d[x]:
                    self.time = max(mt,self.time)
                for e in d[x]:
                    dfs(e,mt+informTime[x])
                    
        dfs(d[-1],0)
        return self.time
        
                
            
            
            
            
            
                


'''
n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]

'''

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node):
            if not graph[node]:
                return 0
            else:
                max_time = 0
                for child in graph[node]:
                    max_time = max(max_time,dfs(child))
                return informTime[node]+max_time
            
        graph = collections.defaultdict(list)
        for i,j in enumerate(manager):
            graph[j].append(i)
            
        return dfs(headID)
        


class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(map(dfs, range(n)))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        sub = defaultdict(list)
        for i, m in enumerate(manager):
            sub[m].append(i)
            
        def dfs(i):
            m = 0
            for j in sub[i]:
                m = max(m, dfs(j))
            return m + informTime[i]
    
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        hmap = {}
        for i, m in enumerate(manager):
            hmap[m] = hmap.get(m, []) + [i]
        
        stack = [(headID, 0)]
        res = 0
        
        while stack:
            m, val = stack.pop()
            res = max(res, val)
            if m not in hmap:
                continue
            val += informTime[m]
            for e in hmap[m]:
                stack.append((e, val))
        
        return res

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # Convert to a tree structure
        
        graph = collections.defaultdict(list)
        for person, boss in enumerate(manager):
            if boss != -1:
                graph[boss].append(person)
            
        # Then do a bfs
        # Person with max_time is the answer
        # Guaranteed to be a tree, no need for seen
        queue = [(headID, 0)]
        max_time = - float('inf')
        
        while queue:
            nq = []
            
            for boss, time in queue:
                max_time = max(max_time, time)
                
                for employee in graph[boss]:
                    nq.append((employee, time + informTime[boss]))
            queue = nq
            
        return max_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = {}
        res = 0
        for e, m in enumerate(manager):
            graph[m] = graph.get(m, []) + [e]
        stack = [(headID, 0)]
        while stack:
            curr, time = stack.pop()
            res = max(res, time)
            if curr in graph:
                for e in graph[curr]:
                    stack.append((e, time + informTime[curr]))
        return res

class Solution:
    def dfs(self,node,visited,graph,minute,informTime):
        visited[node]=minute
        for neighbour in graph[node]:
            self.dfs(neighbour,visited,graph,minute+informTime[node],informTime)
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph={}
        for i in range(n):
            graph[i]=[]
        for i in range(len(manager)):
            if manager[i]!=-1:
                graph[manager[i]]+=[i]
        visited=[-1 for i in range(n)]
        visited[headID]=0
        self.dfs(headID,visited,graph,0,informTime)
        return max(visited)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        d = collections.defaultdict(list)
        
        for i in range(n):
            d[ manager[i] ].append(i)
        
                
        def dfs(i):
            if not d[i]:
                return 0
            
            return informTime[i]+max( [ dfs(t) for t in d[i]  ] )
        
        return dfs( d[-1][0] )
    
        
        
        
        
#         d = collections.defaultdict(list)
#         for i in range(n):
#             d[ manager[i] ].append(i)
        
#         res = 0
#         que = collections.deque( [ [ d[-1][0], 0 ] ] )
        
#         while que:
#             cur, time = que.popleft()
#             res = max(res, time)
#             time += informTime[cur]
            
#             for t in d[cur]:
#                 que.append( [t, time] )
        
#         return res
        


class Solution:
    def helper(self, node, sub, informTime):
        if node not in sub or len(sub[node]) == 0:
            return informTime[node]
        times = [self.helper(x, sub, informTime) for x in sub[node]]
        return max(times) + informTime[node]
    
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        sub = defaultdict(list)
        for i, m in enumerate(manager):
            sub[m].append(i)
        return self.helper(headID, sub, informTime)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def get_inform_time(mgr):
            subords = g[mgr]
            time_to_inform = 0
            for sub in subords:
                time_to_inform = max(time_to_inform, get_inform_time(sub))
                
            return time_to_inform + informTime[mgr]
                
        
        g = collections.defaultdict(list)
        for employee, mgr in enumerate(manager):
            g[mgr].append(employee)
            
        return get_inform_time(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        subordination = collections.defaultdict(list)
        for i, mID in enumerate(manager):
            if mID != -1:
                subordination[mID].append(i)
        
        def dfs(mID: int) -> int:
            maxTime = 0
            for sub in subordination[mID]:
                maxTime = max(maxTime, informTime[mID] + dfs(sub))
            return maxTime
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(i):
            if manager[i] != -1:
                informTime[i] += dfs(manager[i])
                manager[i] = -1
            return informTime[i]
        return max(map(dfs, range(n)))

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for _ in range(n)]
        
        for i, m in enumerate(manager):
            if m >= 0:
                children[m].append(i)
        
        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n, headID, manager, informTime):
        children = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: 
                children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)



class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        for i, m in enumerate(manager):
            if m >= 0: children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)
        # subordinates = [[] for _ in range(n)]
        # for i in range(n):
        #     for j in range(n):
        #         if manager[j] == i:
        #             subordinates[i].append(j)
        # res = [0] * n
#         # print(subordinates)l
#         def helper(id, current_time):
#             time = informTime[id] + current_time
#             subs = subordinates[id]
#             if subs:
#                 for k in subs: helper(k, time)
#             else:
#                 res[id] = time               
        
#         helper(headID, 0)
#         return max(res)
#         queue = deque([(manager.index(-1), 0)])
#         while queue:
#             i, t = queue.popleft()
#             for j in subordinates[i]:
#                 res[j] = t
#                 queue.append((j, t + informTime[i]))
#         return max(res)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        tree = collections.defaultdict(list)
        time = {}
        for i, (m, t) in enumerate(zip(manager, informTime)):
            tree[m].append(i)
            time[i] = t
        
        ans = 0
        
        def dfs(node, t):
            nonlocal ans
            
            t += time[node]
            for child in tree[node]:
                dfs(child, t)
            ans = max(ans, t)
        
        dfs(headID, 0)
        return ans

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # DFS Stack
        self.max = 0
        directSub = self.makeDirectSub(manager)
        self.dfs(headID,directSub,informTime)
        return self.max
        
    def makeDirectSub(self, manager):
        d = {new_list: [] for new_list in range(len(manager))}

        for employee in range(len(manager)):
            if manager[employee] != -1:
                d[manager[employee]].append(employee)
        return d
            
        
    def dfs(self, headID, directSub,informTime):
        stk = [(headID,0)]
        while stk:
            employee, time = stk.pop()
            self.max = max(self.max,time)
            # add all subemployees and record the time it took them to get the information
            for subEmp in directSub[employee]:
                stk.append((subEmp,time+informTime[employee]))
        return


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for _ in range(n)]
        for i, x in enumerate(manager):
            if x>=0: children[x].append(i)
            
        def dfs(p):
            return max([dfs(x) for x in children[p]] or [0]) + informTime[p]
        
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        children = [[] for i in range(n)]
        # construct the tree
        # children[m] is the list of direct subordinates
        # of m
        for i, m in enumerate(manager):
            if m >= 0:
                children[m].append(i)
        
        # the time for a maganer = max(his employee's time)
        # + inforTime[manager]
        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        
        return dfs(headID)

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        # Top down approach is ok
        # Bottom up approach: COPIED
        # Idea is: Given any employee, recursively (going up the chain of command) compute its time to 
        # reach the head. Then, for a different employee, check if its managers computed value is set
        # via the dfs call. If it is, use it directly, else make the dfs call as before, and so on for each employee.
        
        # Lee's solution uses manager as a way to mark if the dfs call for an employee has been made.
        # Let's do it assuming we should not modify manager => maintain a separate array
        # This is basically the usual DFS on the directed graph as provided
        # With each DFS visit, we add the informTime of an employee's manager to the informTime of the employee
        # So informTime will now tell you the time to reach the head from the employee
        # To avoid using visited[], we'd need to modify manager
        
        # def dfs_visit(u):
            # visited[u] = True
            # v = manager[u]
            # if v == -1:
            #     return 0
            # else:
            #     if not visited[v]:
            #         _ = dfs_visit(v)
            #     informTime[u] += informTime[v]
            #     return informTime[u]

        # Without visited, modifying manager
        def dfs_visit(u):
            v = manager[u]
            if manager[v] != -1:
                dfs_visit(v)
            informTime[u] += informTime[v]
            manager[u] = -1
            return informTime[u]
            
        #visited = [False]*n
        res = 0
        for u in range(n):
            # if not visited[u]:
            if manager[u] != -1:
                res = max(res, dfs_visit(u))
        return res
                    


class Solution:
    over_all_max_time = 0
    def DFS(self ,edgeList , max_time , headID , informTime):
        if len(edgeList[headID]) == 0:
            Solution.over_all_max_time = max(Solution.over_all_max_time , max_time)
            return
        
        for emp in edgeList[headID]:
            max_time += informTime[headID]
            self.DFS(edgeList , max_time , emp , informTime)
            max_time -= informTime[headID]
        
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        Solution.over_all_max_time = 0
        edgeList = {i:[] for i in range(n)}
        for cur_emp in range(n):
            cur_emp_manager = manager[cur_emp]
            if cur_emp_manager != -1:
                edgeList[cur_emp_manager].append(cur_emp)
        self.DFS(edgeList , 0 , headID , informTime)
        return Solution.over_all_max_time


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        n = len(manager)
        graph = collections.defaultdict(list)
        
        for i in range(n):
            graph[manager[i]].append(i)
            
            
        q = [(headID, 0)]
        res = 0
        
        while q:
            node, time = q.pop(0)
            res = max(res, time)
            for nei in graph[node]:
                q.append((nei, time + informTime[node]))
        
        return res
        
        


class Solution:

    def numOfMinutes(self, n, headID, manager, informTime):
        time_when_informed = {}
        total = 0

        time_when_informed[headID] = 0

        def get_informed_time(node):
            if node in time_when_informed:
                return time_when_informed[node]
            else:
                ret = informTime[manager[node]] + get_informed_time(manager[node])
                time_when_informed[node] = ret
                return ret

        ans = 0
        for node in range(len(manager)):
            if node not in time_when_informed:
                ans = max(ans, get_informed_time(node))
            else:
                ans = max(ans, time_when_informed[node])

        return ans

from collections import deque

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        visited = set()
        graph = defaultdict(list)
        for idx, m in enumerate(manager):
            graph[m].append(idx)

        max_val = 0        
        q = deque()
        q.append([headID, 0])
        
        while len(q):
            parent, weight = q.popleft()
            max_val = max(max_val, weight)
            for child in graph[parent]:
                q.append((child, weight + informTime[parent]))
        
        return max_val

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        #DFS, find longest path from root to leaf
        #TC: O(N)
        #SC: O(N)
        child = defaultdict(list)
        boss = -1
        res = 0
        for i in range(len(manager)):
            if manager[i] == -1:
                boss = i
                continue
            child[manager[i]].append(i)
        def dfs(i, time):
            nonlocal res
            #time taken for the information to reach i
            # print(i, child[i])
            res = max(res, time)
            for j in range(len(child[i])):
                dfs(child[i][j], time + informTime[i])
        dfs(boss, 0)
        return res


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def dfs(node, cost):
            nonlocal ans
            cost += informTime[node]
            
            ans = max(ans, cost)
            
            for nei in graph[node]:
                if nei not in seen:
                    seen.add(nei)
                    dfs(nei, cost)
        
        graph = collections.defaultdict(list)
        
        for i, man in enumerate(manager):
            if man == -1: continue
            graph[man].append(i)
        
        seen = set()
        
        ans = 0
        
        dfs(headID, 0)
        
        return ans

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
      graph = collections.defaultdict(list)
      for i in range(n):
        graph[manager[i]].append(i)
        
        
      def dfs(manager, curr_time):
        self.max_time = max(self.max_time, curr_time)
        for subordinate in graph[manager]:
          dfs(subordinate, curr_time + informTime[manager])
      
      
      self.max_time = 0
      dfs(headID, 0)
      return self.max_time

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        children = collections.defaultdict(list)
        for i, m in enumerate(manager):
            if m >= 0: children[m].append(i)

        def dfs(i):
            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        managerMap = defaultdict(list)

        for i, v in enumerate(manager):
            managerMap[v].append(i)

        def dfs(mgr):
            return max([dfs(emp) for emp in managerMap[mgr]] or [0]) + informTime[mgr]

        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        def find_ttk(e):
            if ttk[e]==-1:
                m = manager[e]
                if m == -1:
                    ttk[e]=0
                else:
                    ttk[e]=find_ttk(m)+informTime[m]
            return ttk[e]
        
        ttk = [-1]*n
        for e in range(n):
            if ttk[e]==-1:
                ttk[e]=find_ttk(e)
                
        return max(ttk)

from collections import defaultdict
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        sub = defaultdict(list)
        for i, s in enumerate(manager):
            sub[s] += [i]
        
        def dfs(cur):
            return max([dfs(employee) for employee in sub[cur]] or [0]) + informTime[cur]
        return dfs(headID)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        minutes = 0

        # construct adj list
        g = defaultdict(list)
        for i in range(n):
            g[manager[i]].append(i)

        # dfs 
        def dfs(eid, elapsed):
            nonlocal minutes
            if not g[eid]:
                minutes = max(minutes, elapsed)
            for sub in g[eid]:
                dfs(sub, elapsed+informTime[eid])
        dfs(headID, 0)
        return minutes
        


from collections import deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        graph = {}
        
        for emp,manager in enumerate(manager):
            if manager in graph:
                graph[manager].append(emp)
            else:
                graph[manager] = [emp]
                
        ans = {}
        
        ans[headID] = 0
        
        Queue = deque()
        Queue.append(headID)
        maxele = 0
        while Queue:
            cid = Queue.popleft()
            if cid not in graph:
                continue
            for emp in graph[cid]:
                ans[emp] = ans[cid] + informTime[cid]
                maxele = max(maxele, ans[emp])
                Queue.append(emp)
                
        return maxele
            
        
        
        
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        G = {i:[] for i in range(n)} # map node to a list of its children
        for i in range(len(manager)):
            if manager[i] > -1:
                G[manager[i]].append(i)
        self.ans = 0
        def dfs(root=headID,timeUsed=0):
            if not G[root]:
                #self.ans = max(self.ans,timeUsed)
                return timeUsed
            # for child in G[root]:
            #     dfs(child,timeUsed + informTime[root])
            
            return max([dfs(child,timeUsed + informTime[root]) for child in G[root]])
        
        return dfs()
        
        
#         from collections import deque
#         def bfs(root=headID):
#             ans = 0
#             Q = deque()
#             Q.append([root])
            
#             while Q:
#                 nodes = Q.popleft()
#                 ans += max([informTime[node] for node in nodes])
                
#                 next_lvl = []
#                 for node in nodes:
#                     for child in G[node]:
#                         next_lvl.append(child)
#                 if next_lvl:
#                     Q.append(next_lvl)
#             return ans
#         return bfs()


import heapq

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        hierachy = {}
        for idx, m in enumerate(manager):
            if m not in hierachy: 
                hierachy[m] = []
            hierachy[m].append(idx)
            
        time_needed = [-1] * n
        time_needed[headID] = 0

        # Dijkstra's algorithm. There's not really such a need. 
        # There's no need to keep track of 'visited' because each node will be visited once anyway. 
        q = [(0, headID)]
        
        while q:
            cost, node = heapq.heappop(q)
            time_needed[node] = cost
            for nei in hierachy.get(node, []):
                heapq.heappush(q, (time_needed[node] + informTime[node], nei))
                
        return max(time_needed)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        g = defaultdict(list)
        for e,m in enumerate(manager):
            it = informTime[m]
            g[m].append((e,it))
            
        self.mc = 0
        def dfs(node,cost):
            self.mc = max(self.mc, cost)
            
            for child,cc in g[node]:
                dfs(child,cost + cc)
        
        dfs(headID,0)
                
        return self.mc
            
            
            


from collections import defaultdict
from collections import deque
class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        
        eg = defaultdict(set)
        mgr = None
        for i,man in enumerate(manager):
            if man != -1:
                eg[man].add(i)
            else:
                mgr = i
        # print(eg)
        time_map = {}
        for i, time in enumerate(informTime):
            time_map[i] = time
#         we are looking for the max path length when a leaf node is reached
        q = deque()
        q.append((mgr, time_map[mgr]))
        # print(time_map, q)
        max_it = -float('inf')
        
        while q:
            node, dist = q.popleft()
            # print(dist)
            if len(eg[node]) == 0:
                max_it = max(max_it, dist)
            
            for neighbor in eg[node]:
                q.append((neighbor, dist+time_map[neighbor]))
        
        return max_it
        


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        #           headID
        #         /        \\
        #      sub1         sub2
        #      / \\          / \\
        #   sub11 sub12  sub21 sub22
        
        subs = [[] for i in range(n)]
        for i, m in enumerate (manager):
            if m != -1:
                subs[m].append(i)
                
        def my_dfs(m):
            
            if not len(subs[m]): return informTime[m]
            return max([my_dfs(s) for s in subs[m]]) + informTime[m]
        
        return my_dfs(headID)


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        company_dict = {}
        total_time = 0
        
        for i, m in enumerate(manager):
            if m not in company_dict:
                company_dict[m] = set([i])
            else:
                company_dict[m].add(i)
        
        def get_emp_inf_time(manager, time):
            nonlocal total_time
            if manager not in company_dict:
                total_time = max(total_time, time)
                return
            for e in company_dict[manager]:
                time_to_inform = time + informTime[manager]
                get_emp_inf_time(e, time_to_inform)
        
        head = list(company_dict[-1])[0]
        get_emp_inf_time(head, 0)
        return total_time