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:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(list(map(dfs, manager)))\n        \n            \n", "class Solution:\n    def numOfMinutes(self, n, headID, manager, informTime):\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(list(map(dfs, list(range(n)))))\n", "# class Node:\n#     def __init__(self, id: int, inform_t: int):\n#         self.id = id\n#         self.children = []\n#         self.inform_t = inform_t\n    \n#     def __repr__(self):\n#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'\n    \n#     def total_inform_time(self):\n#         t = self.inform_t\n#         if self.children:\n#             t += max(ch.total_inform_time() for ch in self.children)\n#         return t\n\n# class Solution:\n    \n#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:\n#         nodes = [None] * len(manager)\n#         root = None\n#         for id, man_id in enumerate(manager):\n#             if nodes[id] is None:\n#                 nodes[id] = Node(id, inform_time[id])\n            \n#             if man_id >= 0:\n#                 if nodes[man_id] is None:\n#                     nodes[man_id] = Node(man_id, inform_time[man_id])\n\n#                 nodes[man_id].children.append(nodes[id])\n#             else:\n#                 root = nodes[id]\n#         return root\n    \n    \n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n#         root = self.build_tree(manager, inform_time)\n#         return root.total_inform_time()\n    \n\n# Top down\n# class Solution:\n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n#         children = [[] for _ in range(n)]\n#         for id, man_id in enumerate(manager):\n#             if man_id >= 0:\n#                 children[man_id].append(id)\n        \n#         def dfs(id):\n#             t = inform_time[id]\n#             if children[id]:\n#                 t += max(dfs(ch) for ch in children[id])\n#             return t\n        \n#         return dfs(head_id)\n \n    \n# Bottom up\n# class Solution:\n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n        \n#         def dfs(id):\n#             if manager[id] >= 0:\n#                 inform_time[id] += dfs(manager[id])\n#                 manager[id] = -1\n#             return inform_time[id]\n        \n#         return max(dfs(id) for id in range(n))\n\n\n# Bottom up with cache\nclass Solution:\n    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n        cache = [None] * n\n        \n        def dfs(id):\n            if cache[id]:\n                return cache[id]\n            \n            t = inform_time[id]\n            if manager[id] >= 0:\n                t += dfs(manager[id])\n            \n            cache[id] = t\n            return t\n        \n        return max(dfs(id) for id in range(n))\n", "\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        \n        reports = {}\n        for i,e in enumerate(manager):\n            if e not in reports:\n                reports[e] = []\n            reports[e].append(i)\n                \n        accum = [0]*n\n        todo = [-1]\n        while todo:\n            curr = todo.pop()\n            mxxR = 0\n            if curr not in reports:\n                continue\n            for r in reports[curr]:\n                todo.append(r)\n                accum[r] += informTime[r] + accum[manager[r]]\n        return max(accum)\n                \n            \n                \n        \n#         talktime = {}\n#         mxx = -1\n#         for i,m in enumerate(manager):\n#             mxx = max(mxx, self.calc(i, manager, informTime))\n#         return mxx\n                \n#     def calc(self,e, manager, informTime):\n#         if e == -1:\n#             return 0\n#         return informTime[e] + self.calc(manager[e], manager, informTime)\n        \n        \n", "class Solution:\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = {i: [] for i in range(n)}\n        for i in range(n): \n            if manager[i] >= 0:\n                graph[manager[i]].append(i)\n                \n        to_inform = deque([(headID, 0)])\n        max_t = 0\n        while to_inform:\n            mid, t = to_inform.pop()\n            new_t = t + informTime[mid]\n            max_t = max(max_t, new_t)\n            for s in graph[mid]:\n                to_inform.append((s, new_t))\n            \n        return max_t", "class Node:\n    def __init__(self, val):\n        self.val = val\n        self.subordinates = []\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = [Node(t) for t in informTime]\n\n        root = None\n        for k, v in enumerate(manager):\n            if v >= 0:\n                nodes[v].subordinates.append(nodes[k])\n            else:\n                root = nodes[k]\n\n        ans = 0\n\n        def dfs(node, path):\n            nonlocal ans\n            if not node.subordinates:\n                ans = max(ans, path + node.val)\n                return\n            for n in node.subordinates:\n                dfs(n, n.val + path)\n\n        dfs(root, root.val)\n\n        return ans\n\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n\n        for k, v in enumerate(manager):\n            if v >= 0:\n                children[v].append(k)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n\n        return dfs(headID)\n\n\n\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n <= 1 and manager[0] == -1:\n            return informTime[0]\n        subordinates = defaultdict(list)\n        for empId in range(len(manager)):\n             subordinates[manager[empId]].append(empId)\n        def dfs(sid,informTime):\n            maxtime = 0\n            for subId in subordinates[sid]:\n                maxtime = max(maxtime,dfs(subId,informTime))\n            return (maxtime+informTime[sid])\n        return dfs(headID,informTime)\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = collections.defaultdict(set)\n        for sub, mag in enumerate(manager):\n            subs[mag].add(sub)\n        \n        heap, time = [(informTime[headID], headID)], 0\n        while heap:\n            time = heap[0][0]\n            while heap and heap[0][0] == time:\n                _, mag = heapq.heappop(heap)\n                for sub in subs[mag]:\n                    heapq.heappush(heap, (time + informTime[sub], sub))\n        return time\n        \n            \n", "  \nclass Solution:\n    # 1152\n    def numOfMinutes(self, n, headID, manager, informTime):\n       # @lru_cache(None)\n        def myTime(myBoss):\n            if manager[myBoss] > -1:\n                informTime[myBoss] += myTime(manager[myBoss])\n                manager[myBoss] = -1\n                \n            return informTime[myBoss]\n        return max(map(myTime, manager))", "from collections import deque\n\nclass Solution:\n    def build_graph(self, n, manager):\n        graph = {i: [] for i in range(n)}\n        for i, m in enumerate(manager):\n            if m == -1:\n                continue\n            graph[m].append(i)\n        return graph\n            \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = self.build_graph(n, manager)\n        if not graph[headID]:\n            return 0\n        \n        queue = deque([(headID, informTime[headID])])\n        t = 0\n        informed = set()\n        while queue:\n            boss, time = queue.popleft()\n            t = max(t, time)\n            for employee in graph[boss]:\n                if employee in informed:\n                    continue\n                queue.append((employee, time + informTime[employee]))\n                informed.add(employee)\n        return t", "# class Node:\n#     def __init__(self, id: int, inform_t: int):\n#         self.id = id\n#         self.children = []\n#         self.inform_t = inform_t\n    \n#     def __repr__(self):\n#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'\n    \n#     def total_inform_time(self):\n#         t = self.inform_t\n#         if self.children:\n#             t += max(ch.total_inform_time() for ch in self.children)\n#         return t\n\n# class Solution:\n    \n#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:\n#         nodes = [None] * len(manager)\n#         root = None\n#         for id, man_id in enumerate(manager):\n#             if nodes[id] is None:\n#                 nodes[id] = Node(id, inform_time[id])\n            \n#             if man_id >= 0:\n#                 if nodes[man_id] is None:\n#                     nodes[man_id] = Node(man_id, inform_time[man_id])\n\n#                 nodes[man_id].children.append(nodes[id])\n#             else:\n#                 root = nodes[id]\n#         return root\n    \n    \n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n#         root = self.build_tree(manager, inform_time)\n#         return root.total_inform_time()\n    \n\n# Top down\n# class Solution:\n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n#         children = [[] for _ in range(n)]\n#         for id, man_id in enumerate(manager):\n#             if man_id >= 0:\n#                 children[man_id].append(id)\n        \n#         def dfs(id):\n#             t = inform_time[id]\n#             if children[id]:\n#                 t += max(dfs(ch) for ch in children[id])\n#             return t\n        \n#         return dfs(head_id)\n \n    \n# Bottom up\nclass Solution:\n    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n        \n        def dfs(id):\n            if manager[id] >= 0:\n                inform_time[id] += dfs(manager[id])\n                manager[id] = -1\n            return inform_time[id]\n        \n        return max(dfs(id) for id in range(n))\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        #           headID\n        #         /        \\\\\n        #      sub1         sub2\n        #      / \\\\          / \\\\\n        #   sub11 sub12  sub21 sub22\n        \n        subs = [[] for i in range(n)]\n        for i, m in enumerate (manager):\n            if m != -1:\n                subs[m].append(i)\n                \n        def my_dfs(root):\n            \n            if subs[root] is None: return informTime[root]\n            \n            return max([my_dfs(s) for s in subs[root]] or [0]) + informTime[root]\n        \n        return my_dfs(headID)\n            \n        \n        \n#     def numOfMinutes(self, n, headID, manager, informTime):\n#         children = [[] for i in xrange(n)]\n#         for i, m in enumerate(manager):\n#             if m >= 0: children[m].append(i)\n\n#         def dfs(i):\n#             return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n#         return dfs(headID)\n\n    # def dfs(i):\n    #         if manager[i] != -1:\n    #             informTime[i] += dfs(manager[i])\n    #             manager[i] = -1\n    #         return informTime[i]\n    #     return max(map(dfs, range(n)))\n", "class Solution:\n    def __init__(self):\n        self.res = 0\n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(set) \n        for i, m in enumerate(manager):\n            graph[m].add(i)\n        def helper(emp, time):\n            if emp not in graph:\n                self.res = max(self.res, time)\n                return\n            for e in graph[emp]:\n                helper(e, time + informTime[emp])\n        helper(headID, 0)\n        return self.res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n\n        children = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n#         DFS\n        def dfs(employee):\n            if manager[employee] != -1:\n                informTime[employee] += dfs(manager[employee])\n                manager[employee] = -1\n            return informTime[employee]\n        return max(list(map(dfs, list(range(n)))))\n#         BFS\n#         companyTree = defaultdict(list)\n        \n#         for idx, head in enumerate(manager):\n#             if head != -1:\n#                 companyTree[head].append(idx)\n#         # use heap \n#         queue = deque([(headID, 0)])\n#         visited = set()\n#         res = 0\n        \n#         while queue and len(visited) < n:\n#             cur_employee, cur_total = queue.popleft()\n#             res = max(res, cur_total + informTime[cur_employee])\n#             for subord in companyTree[cur_employee]:\n#                 queue.append((subord, cur_total + informTime[cur_employee]))\n#         return res\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n <= 1:\n            return 0\n        res = 0\n        childs = defaultdict(list)\n        for idx, parent in enumerate(manager):\n            childs[parent].append(idx)\n\n        queue = deque([(headID, informTime[headID])])\n        while queue:\n            cur_id, cur_time = queue.popleft()\n            # calculate max\n            res = max(res, cur_time)\n            for child in childs[cur_id]:\n                queue.append((child, cur_time + informTime[child]))\n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # create graph\n        graph = collections.defaultdict(list)\n        for idx, mgr in enumerate(manager):\n            if idx == headID:\n                continue \n                \n            graph[mgr].append(idx)\n        \n        max_time = 0\n        def dfs(start):\n            nonlocal max_time\n            if start is None:\n                return 0\n        \n            curr_time = 0\n            for child in graph[start]:\n                curr_time = max(curr_time, dfs(child))\n                \n            max_time = max(max_time, curr_time + informTime[start])\n            \n            return curr_time + informTime[start]\n        \n        dfs(headID)\n        \n        return max_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        employees_of_manager = [[] for i in range(n)]\n        for e, m in enumerate(manager):\n            # print(m)\n            if m >= 0: \n                employees_of_manager[m].append(e)\n\n        def dfs(i):\n            return max([dfs(j) for j in employees_of_manager[i]] or [0]) + informTime[i]\n        return dfs(headID)", "def createGraph(manager: List[int]):\n    graph = collections.defaultdict(set)\n    for i, employee in enumerate(manager):\n        graph[employee].add(i)\n    return graph\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = createGraph(manager)\n        stack = [(0, headID)]\n        ans = 0\n        while stack:\n            depth, employeeId = stack.pop()\n            if manager[employeeId] != -1:\n                informTime[employeeId] += informTime[manager[employeeId]]\n            ans = max(informTime[employeeId], ans)\n            for employee in graph[employeeId]:\n                stack.append((depth+1, employee))\n        return ans", "class Solution:\n    def build_graph(self,n,manager,informTime,headID):\n        \n        graph={x:[] for x in range(n)}\n        \n        for i in range(n):\n\n            mgr=manager[i]\n            emp=i\n            \n            if mgr == -1: continue\n            \n            if graph.get(mgr,0):\n                graph[mgr].append(emp)\n            else:\n                graph[mgr]=[emp]\n        \n        return graph\n    def traverse_graph(self, graph, headID, informTime):\n        result=0\n        \n        for v in graph[headID]:\n            result = max(result, self.traverse_graph(graph, v, informTime));\n        \n        return result+informTime[headID]\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph=self.build_graph(n,manager,informTime, headID)\n        return self.traverse_graph(graph, headID, informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        delays = [-1] * n\n        \n        def delay(id: int):\n            if delays[id] >= 0:\n                return delays[id]\n            \n            myman = manager[id]\n            if myman < 0:\n                delays[id] = 0\n                return 0\n            \n            mandelay = delay(myman) + informTime[myman]\n            delays[id] = mandelay\n            return delays[id]\n        \n        return max(delay(i) for i in range(n))\n            \n\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        def dfs(employee, time):\n            self.result = max(self.result, time)\n            for sub in subordinates[employee]:\n                dfs(sub, time + informTime[employee])\n            \n        subordinates = collections.defaultdict(list)\n        self.result = 0\n        for i, m in enumerate(manager):\n            if i != headID:\n                subordinates[m].append(i)\n        dfs(headID, 0)\n        return self.result\n            \n        \n    # def dfs(self, id):\n    #     return max(informTime[id] + self.dfs(sub) for sub in subordinates[id]) if id in subordinates else 0\n", "def createGraph(manager: List[int]):\n    graph = collections.defaultdict(set)\n    for i, employee in enumerate(manager):\n        graph[employee].add(i)\n    return graph\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = createGraph(manager)\n        stack = [(0, headID)]\n        visited = set()\n        while stack:\n            depth, employeeId = stack.pop()\n            if employeeId not in visited:\n                visited.add(employeeId)\n                if manager[employeeId] != -1:\n                    informTime[employeeId] += informTime[manager[employeeId]]\n                for employee in graph[employeeId]:\n                    stack.append((depth+1, employee))\n        return max(informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = {i:[] for i in range(n)}\n        for child, parent in enumerate(manager):\n            if parent >= 0:\n                children[parent].append(child)\n        \n        def dfs(i):\n            return max([dfs(child) for child in children[i]], default=0) + informTime[i]\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(list)\n        \n        for i in range(len(manager)):\n            graph[manager[i]].append((informTime[i], i))\n        heap = [(informTime[headID], headID)]\n        # dic = {}\n        mx = -1\n        while heap:\n            time, index = heapq.heappop(heap)\n            mx = max(mx,time)\n\n            for t,n in graph[index]:\n                heapq.heappush(heap, (t+time, n))\n        return mx#max(dic.values())\n", "\nclass Solution:\n    def findLongestPath(self, tree, root, informTime):\n        return max([self.findLongestPath(tree, child, informTime) for child in tree[root]] + [0]) + informTime[root]\n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        mapM2E = collections.defaultdict(list)\n        for i in range(n):\n            if i == headID:\n                continue\n            else:\n                mapM2E[manager[i]].append(i)\n        \n        return self.findLongestPath(mapM2E, headID, informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager2employee = defaultdict(list)\n        for employee, manager in enumerate(manager):\n            manager2employee[manager].append(employee)\n        \n        def dfs(manager):\n            if not manager2employee[manager]:\n                return 0\n            return max([informTime[manager] + dfs(e) for e in manager2employee[manager]])\n        return dfs(headID)", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        res = 0\n        nextdict = defaultdict(set)\n        timedict = []\n        for i1, m in enumerate(manager):\n            nextdict[m].add(i1)\n        for t in informTime:\n            timedict.append(t)\n        \n        visit = set()\n        q = [(headID, 0)]\n        while q:\n            this = q[-1]\n            visit.add(this[0])\n            flag = False\n            for nexte in nextdict[this[0]]:\n                if nexte not in visit:\n                    q.append((nexte, this[1]+timedict[this[0]]))\n                    flag = True\n                    break\n            if not flag:\n                res = max(res, q.pop()[1])\n        return res\n        \n", "# class Node:\n#     def __init__(self, id: int, inform_t: int):\n#         self.id = id\n#         self.children = []\n#         self.inform_t = inform_t\n    \n#     def __repr__(self):\n#         return f'<{self.id} ({self.inform_t}): {len(self.children)}>'\n    \n#     def total_inform_time(self):\n#         t = self.inform_t\n#         if self.children:\n#             t += max(ch.total_inform_time() for ch in self.children)\n#         return t\n\n# class Solution:\n    \n#     def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:\n#         nodes = [None] * len(manager)\n#         root = None\n#         for id, man_id in enumerate(manager):\n#             if nodes[id] is None:\n#                 nodes[id] = Node(id, inform_time[id])\n            \n#             if man_id >= 0:\n#                 if nodes[man_id] is None:\n#                     nodes[man_id] = Node(man_id, inform_time[man_id])\n\n#                 nodes[man_id].children.append(nodes[id])\n#             else:\n#                 root = nodes[id]\n#         return root\n    \n    \n#     def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n#         root = self.build_tree(manager, inform_time)\n#         return root.total_inform_time()\n    \n\nclass Solution:\n    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n        children = [[] for _ in range(n)]\n        for id, man_id in enumerate(manager):\n            if man_id >= 0:\n                children[man_id].append(id)\n        \n        def dfs(id):\n            t = inform_time[id]\n            if children[id]:\n                t += max(dfs(ch) for ch in children[id])\n            return t\n        \n        return dfs(head_id)\n", "class Solution:\n    res = 0\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if not manager or not informTime: return 0\n        dic = {-1: [[headID, informTime[headID]]]}\n        for i in range(len(manager)):\n            if manager[i] not in dic:\n                dic[manager[i]] = []\n            dic[manager[i]].append([i, informTime[i]])\n        \n        def dfs(dic: {}, id: int, cur: int) -> None:\n            if id not in dic:\n                self.res = max(self.res, cur);\n                return\n            \n            for employee in dic[id]:\n                dfs(dic, employee[0], cur + employee[1])\n            \n        dfs(dic, -1, 0)\n        \n        return self.res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        time = [-1] * n\n        time[headID] = 0\n        result = 0\n        \n        for i in range(n):\n            if time[i] == -1:\n                # search down a path\n                index = i\n                path = []\n                \n                while time[index] == -1:\n                    path.append(index)\n                    index = manager[index]\n                \n                for j in reversed(path):\n                    time[j] = time[manager[j]] + informTime[manager[j]]\n                    result = max(result, time[i])\n            \n        return result", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        import heapq\n        uninformed = set([i for i in range(n)])\n        q = [(0,headID)]\n        heapq.heapify(q)\n        sub = collections.defaultdict(list)\n        for i,v in enumerate(manager):\n            sub[v].append(i)\n        while q:\n            # print(q)\n            # print(uninformed)\n            TI, ID = heapq.heappop(q)\n            uninformed -= set([(ID)])\n            if not uninformed: return TI\n            for sb in sub[ID]:\n                if sb in uninformed: heapq.heappush(q,(TI+informTime[ID],sb))\n        return -1\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        \n        for i, managerId in enumerate(manager):\n            graph[managerId].append((informTime[i], i))\n        \n        dist = {}\n        heap = [(informTime[headID], headID)] \n        \n        while heap:\n            time, u = heapq.heappop(heap)\n            if u in dist:\n                continue\n            dist[u] = time    \n            for w, v in graph[u]:\n                if v in dist:\n                    continue\n                heapq.heappush(heap, (time+w, v))    \n        return max(dist.values()) ", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        return self.DFS(n, headID, manager, informTime)\n\n        \n    def BFS(self, n: int, headID: int, manager: List[int], informTime: List[int]):\n        graph = defaultdict(list)\n        for i in range(n):\n            graph[manager[i]].append((i, informTime[manager[i]]))\n        \n        q = deque([(headID, 0)])\n        max_time = 0\n        while q:\n            node, t = q.popleft()\n            max_time = max(max_time, t)\n            for sub_ord, inform_time in graph[node]:\n                q.append((sub_ord, inform_time + t))\n        \n        return max_time\n    \n    def DFS(self, n, headID, manager, informTime):\n        graph = defaultdict(list)\n        for i in range(n):\n            graph[manager[i]].append((i, informTime[manager[i]]))\n\n        def DFS_helper(node, graph, cur_time):\n            nonlocal max_time\n\n            max_time = max(max_time, cur_time)\n            for sub_ord, inform_time in graph[node]:\n                DFS_helper(sub_ord, graph, cur_time + inform_time)\n                \n\n            \n        max_time = 0\n        DFS_helper(headID, graph, 0)\n        return max_time\n        \n        \n        \n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(list)\n        for i in range(len(manager)):\n            graph[manager[i]].append(i)  \n        q = deque([(headID, 0)])\n        res = 0\n        while q:\n            node, time = q.popleft()\n            res = max(res, time)\n            for nei in graph[node]:\n                q.append((nei, time + informTime[node]))\n        \n        return res\n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinates = collections.defaultdict(list)\n        self.res = 0\n        for i, v in enumerate(manager):\n            subordinates[v].append(i)\n        \n        def dfs(manager, time):\n            self.res = max(self.res, time)\n            for subordinate in subordinates[manager]:\n                dfs(subordinate, time + informTime[manager])\n        dfs(headID, 0)        \n        return self.res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        time = [-1 for _ in range(n)]\n        time[headID] = 0\n        result = 0\n        for i in range(n):\n            if time[i] == -1:\n                index = i\n                path = []\n                while time[index] == -1:\n                    path.append(index)\n                    index = manager[index]\n                for employee in reversed(path):\n                    time[employee] = time[manager[employee]] + informTime[manager[employee]]\n            result = max(result, time[i])\n        return result            \n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        adjacency = collections.defaultdict(list)\n        for i, manager_id in enumerate(manager):\n            adjacency[manager_id].append(i)\n\n        result = 0\n\n        def traverse(worker_id, time):\n            nonlocal result\n            time += informTime[worker_id]\n            result = max(result, time)\n            list(map(lambda x: traverse(x, time), adjacency[worker_id]))\n\n        traverse(headID, 0)\n        return result", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        hierarchy = defaultdict(set)\n        for index,higher in enumerate(manager):\n            hierarchy[higher].add(index)##be careful about what variables you add.\n        times = defaultdict(int)\n        def computeTotalTime(start):\n            if start in times:\n                return times[start]\n            else:\n                answer = 0\n                for lower in hierarchy[start]:\n                    answer = max(answer,computeTotalTime(lower))\n                answer += informTime[start]\n                times[start] = answer\n                return answer\n        return computeTotalTime(headID)", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(n):\n            if n not in tree:\n                return 0\n            return informTime[n] + max(dfs(k) for k in tree[n])\n            \n        tree = defaultdict(list)\n        for i, v in enumerate(manager):\n            if v == -1:\n                continue\n            tree[v].append(i)\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager_employee_dict = {}\n        for i in range(n):\n            m = manager[i] # manager of i is n\n            if m != -1:\n                if m in manager_employee_dict:\n                    manager_employee_dict[m].append(i)\n                else:\n                    manager_employee_dict[m] = [i]\n        \n        # want to start with the head node to get the max depth\n        def chain_length(em):\n            if em not in manager_employee_dict:\n                return 0\n            return informTime[em] + max(chain_length(em_n) for em_n in manager_employee_dict[em])\n        if len(manager_employee_dict) == 0:\n            return 0\n        # num = max(chain_length(e) for e in manager_employee_dict)\n        return chain_length(headID)\n        \n        \n                    \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinates = collections.defaultdict(list)\n        for idx,man in enumerate(manager):\n            subordinates[man].append(idx)\n        from collections import deque\n        queue = deque()\n        queue.append((headID, 0))\n        ans = 0\n        while queue:\n            node,time = queue.popleft()\n            ans = max(ans, time)\n            for sub in subordinates[node]:\n                queue.append((sub, time+informTime[node]))\n        return ans", "from collections import defaultdict, deque\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(list)\n        \n        for e, m in enumerate(manager):\n            graph[m].append(e)\n        \n        res = 0\n        \n        queue = deque([(headID, informTime[headID])])\n        \n        while queue:\n            size = len(queue)\n   \n            employee, time = queue.popleft()\n            res = max(res, time)\n            if employee in graph:\n                for nei in graph[employee]:\n                    queue.append((nei, time + informTime[nei]))\n            \n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        \n        for index, m in enumerate(manager):\n            if m >= 0:\n                children[m].append(index)\n        \n        def dfs(ID):\n            if children[ID]:\n                return max(dfs(j) for j in children[ID]) + informTime[ID]\n            \n            return informTime[ID]\n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        def dfs(emp_id):\n            \n            # no subordinates\n            if not graph[emp_id]:\n                return 0\n            max_path = float('-inf')\n            for subordinate, time in graph[emp_id]:\n                max_path = max(max_path, time+dfs(subordinate))\n            return max_path\n        \n        # create graph from boss -> [(emp,informtime)]\n        graph = collections.defaultdict(list)\n        for emp, boss in enumerate(manager):\n            graph[boss].append((emp,informTime[boss]))\n        del graph[-1]\n        return dfs(headID)", "from typing import List\nfrom collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager_dict = defaultdict(list)\n        for index, curr_manager in enumerate(manager):\n            manager_dict[curr_manager].append(index)\n\n        return self.dfs_num_of_minutes(headID, manager_dict, informTime)\n\n    def dfs_num_of_minutes(self, curr_id, manager_dict, informTime):\n        curr_inform_time = informTime[curr_id]\n\n        direct_report_informa_time = 0\n        for direct_report in manager_dict.get(curr_id, []):\n            direct_report_informa_time = max(direct_report_informa_time, self.dfs_num_of_minutes(direct_report, manager_dict, informTime))\n        \n        return curr_inform_time + direct_report_informa_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(id: int) -> int:\n            return max(informTime[id] + dfs(sub) for sub in subordinates[id]) if id in subordinates else 0\n        \n        subordinates = collections.defaultdict(list)\n        for i, m in enumerate(manager):\n            if i != headID:  #instead of m != -1\n                subordinates.setdefault(m,[]).append(i)\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        \n        for index, m in enumerate(manager):\n            if m >= 0:\n                children[m].append(index)\n        \n        def dfs(ID):\n            return max([dfs(j) for j in children[ID]] or [0]) + informTime[ID]\n        \n        return dfs(headID)", "from collections import deque\nclass Solution:\n    def numOfMinutes(self, n, headID, manager, informTime):\n        memo = [None] * n\n        memo[headID] = 0\n        for uid in range(n):\n            self.dfs(uid, manager, informTime, memo)\n        return max(memo)\n    \n    def dfs(self, uid, manager, informTime, memo):\n        if memo[uid] is not None:\n            return memo[uid]\n        \n        memo[uid] = self.dfs(manager[uid], manager, informTime, memo) + informTime[manager[uid]]\n        return memo[uid]", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n\n        # M[m] = list of employees reporting to m\n        M = [[] for m in range(n)]\n        for i, m in enumerate(manager):\n            if m == -1:\n                continue\n            M[m].append(i)\n\n        def dfs(id, t):\n            t_after_informed = t + informTime[id]\n            return max(dfs(sub_id, t_after_informed) for sub_id in M[id]) if M[id] else t_after_informed\n\n        return dfs(headID, 0)\n\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        managerGraph = collections.defaultdict(list)\n        \n        for i, v in enumerate(manager):\n            managerGraph[v].append(i)\n            \n        res = 0\n        queue = collections.deque([(headID, 0)])\n        while queue:\n            node, time = queue.popleft()\n            res = max(res, time)\n            for nei in managerGraph[node]:\n                queue.append((nei, time + informTime[node]))\n                \n        return res", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        def group_by_manager(l):\n            d = defaultdict(lambda: [])\n            \n            for ind, manager in l:\n                d[manager].append(ind)\n            return d\n        \n        manager_to_subs = group_by_manager(enumerate(manager))\n        def get_children(m):\n            return manager_to_subs.get(m, [])\n        # calculate the maximum path as the max of all the max paths of the subtrees\n        def max_path(r):\n            children = get_children(r)\n            return informTime[r] + (max(max_path(c) for c in children) if children else 0)\n        \n        return max_path(headID)", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        res = 0\n        nextdict = defaultdict(set)\n        timedict = defaultdict(int)\n        for i1, m in enumerate(manager):\n            nextdict[m].add(i1)\n        for i1, t in enumerate(informTime):\n            timedict[i1] = t\n        \n        visit = set()\n        q = [(headID, 0)]\n        while q:\n            this = q[-1]\n            visit.add(this[0])\n            flag = False\n            for nexte in nextdict[this[0]]:\n                if nexte not in visit:\n                    q.append((nexte, this[1]+timedict[this[0]]))\n                    res = max(res, this[1]+timedict[this[0]])\n                    flag = True\n                    break\n            if not flag:\n                q.pop()\n        return res\n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def helper(boss_to_sub, informTime, start):\n            return informTime[start] + max(helper(boss_to_sub, informTime, i) for i in boss_to_sub[start] ) if boss_to_sub[start] else 0\n        boss_to_sub = defaultdict(list)\n        for i, m in enumerate(manager):\n            boss_to_sub[m].append(i)\n        del boss_to_sub[-1]\n        return helper(boss_to_sub, informTime, headID)\n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        g = collections.defaultdict(set)\n        for e, m in enumerate(manager):\n            g[m].add(e)\n            \n        visited = dict()\n        def dfs(node):\n            #if node == n  or informTime[node] == n:\n            #    return 0\n            \n            total = 0\n            for nei in g[node]:\n                total = max(total, dfs(nei) + informTime[node])\n            return total\n        \n        return dfs(headID)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        children = [[] for _ in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: \n                children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        @lru_cache(None)\n        def helper(emp):\n            if manager[emp]>=0:\n                informTime[emp]+=helper(manager[emp])\n                manager[emp]= -1\n            return informTime[emp]\n        return max(map(helper,manager))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        \n        \n        # my solution ... 1744 ms ... 48 % ... 68.7 MB ... 0 %\n        #  time: O(n)\n        # space: O(n)\n        \n        def func(parent, t):\n            tt = t + informTime[parent]\n            self.res = max(self.res, tt)\n            for child in subs[parent]:\n                func(child, tt)\n        \n        subs = collections.defaultdict(set)\n        for i,m in enumerate(manager):\n            if m != -1:\n                subs[m].add(i)\n        self.res = 0\n        func(headID, 0)\n        return self.res\n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        m = collections.defaultdict(list)\n        for sub, mag in enumerate(manager):\n            m[mag].append(sub)\n        \n        def dfs(i):\n            if not m[i]:\n                return informTime[i]\n            return max(dfs(j) for j in m[i]) + informTime[i]\n        return dfs(headID)\n        \n        \n        \n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(list(map(dfs, list(range(len(manager))))))\n        \n            \n", "# class Solution:\n#     def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n# #BFS\n#         stack = [(headID, 0)]\n        \n#         ans = 0\n#         dic = {}\n#         for e, m in enumerate(manager):\n#             dic[m] = dic.get(m, set())\n#             dic[m].add(e)\n            \n#         while stack:\n#             em, time = stack.pop()\n#             if informTime[em] == 0:\n#                 ans = max(ans, time)\n#             else:\n#                 for e in dic.get(em, []):\n#                     stack.append((e, informTime[em]+ time))\n#         return ans\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        \n        for i, managerId in enumerate(manager):\n            graph[managerId].append((informTime[i], i))\n        \n        dist = {}\n        heap = [(informTime[headID], headID)] \n        \n        while heap:\n            time, u = heapq.heappop(heap)\n            if u in dist:\n                continue\n            dist[u] = time    \n            for w, v in graph[u]:\n                if v in dist:\n                    continue\n                heapq.heappush(heap, (time+w, v))    \n        return max(dist.values()) ", "class TreeNode:\n    def __init__(self, val):\n        self.val = val\n        self.children = []\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        # max sum path\n        \n        # # O(N^2)\n        # def build_tree(root_id):\n        #     node = TreeNode(informTime[root_id])\n        #     for idx, m in enumerate(manager):\n        #         if m == root_id:\n        #             node.children.append(build_tree(idx))\n        #     return node\n                \n        # O(N)\n        nodes = []\n        \n        for idx, _ in enumerate(manager):\n            nodes.append(TreeNode(informTime[idx]))\n            \n        for idx, m in enumerate(manager):\n            if idx != headID:\n                nodes[m].children.append(nodes[idx])\n        \n        # root\n        root = nodes[headID]\n        \n        # O(N) time, O(1) space\n        path_sum = 0\n        max_path_sum = 0\n        \n        def dfs(node):            \n            nonlocal path_sum\n            nonlocal max_path_sum\n            \n            if not node.children:                \n                max_path_sum = max(max_path_sum, path_sum + node.val)\n                return\n            \n            for child in node.children:                \n                path_sum += node.val                \n                dfs(child)\n                path_sum -= node.val\n                \n        dfs(root)\n        \n        return max_path_sum\n            \n            \n            \n            \n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = [{} for _ in range(n)]\n        for u, v in enumerate(manager):\n            if v != -1:\n                graph[v][u] = informTime[v]\n        # print(graph)\n        dist = {}\n        pq = [(0, headID)]\n        dist[headID] = 0\n        while pq:\n            t, node = heapq.heappop(pq)\n            for nei in graph[node]:\n                if nei not in dist or graph[node][nei] + t < dist[nei]:\n                    dist[nei] = graph[node][nei] + t\n                    heapq.heappush(pq, (dist[nei], nei))\n        return max(dist.values())\n        \n", "import heapq\n\nfrom collections import defaultdict, deque\n\n\nclass Solution(object):\n    def numOfMinutes(self, n, headID, manager, informTime):\n        if not manager or not informTime: return 0\n        sub = defaultdict(list)\n        q = [(0, headID)]\n        heapq.heapify(q)\n        used = {}\n        for i in range(len(manager)):\n            sub[manager[i]].append(i)\n        while q:\n            spent, emp = heapq.heappop(q)\n            if used.get(emp, -1) != -1: continue\n            used[emp] = spent\n            for next_emp in sub[emp]:\n                if used.get(next_emp, -1) == -1:\n                    heapq.heappush(q, (spent + informTime[emp], next_emp))\n        return max(used.values())", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n\n        def dfs(node, currTime):\n            nonlocal ans\n            \n            if node not in graph:\n                ans = max(ans, currTime)\n            \n            for nei in graph[node]:\n                dfs(nei, currTime + informTime[node])\n        \n        graph = defaultdict(list)\n        for u, v in enumerate(manager):\n            graph[v].append(u)\n \n        ans = 0\n        dfs(headID, 0)\n        return ans\n", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        sub = defaultdict(list)\n        for i, s in enumerate(manager):\n            sub[s] += [i]\n        \n        def dfs(cur, tot):\n            if cur not in sub:\n                return tot\n            high = max(dfs(employee, tot) + informTime[cur] for employee in sub[cur])\n            return tot + high\n        return dfs(headID, 0)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        tree = collections.defaultdict(list)\n        for employee, manager in enumerate(manager):\n            if employee != headID:\n                tree[manager].append(employee)\n        \n        def _maxDepth(node, dist):\n            if node not in tree:\n                return 0\n            \n            return max(_maxDepth(child, informTime[child]) for child in tree[node]) + dist\n        \n        return _maxDepth(headID, informTime[headID])", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n#         res = 0\n#         graph = defaultdict(list)\n#         for index, parent in enumerate(manager):\n#             graph[parent].append(index)\n        \n#         queue = deque([(headID, 0)])\n#         while queue:\n#             curId, curTime = queue.popleft()\n#             res = max(res, curTime)\n#             for child in graph[curId]:\n#                 queue.append((child, curTime + informTime[child]))\n#         return res\n        \n        \n        \n        \n        \n        \n        \n        rst = 0\n        childs = defaultdict(list)\n        for idx, parent in enumerate(manager):\n            childs[parent].append(idx)\n\n        q = deque([(headID, informTime[headID])])\n        while q:\n            cur_id, cur_time = q.popleft()\n            # calculate max\n            rst = max(rst, cur_time)\n            for child in childs[cur_id]:\n                q.append((child, cur_time + informTime[child]))\n        return rst", "def inform(head, subs, informTime) -> int:\n    subordinates = subs[head]\n    if not subordinates:\n        return 0\n    return informTime[head] + max(inform(sub, subs, informTime) for sub in subordinates)\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = [[] for _ in range(n)]\n        for sub, man in enumerate(manager):\n            if man >= 0:\n                subs[man].append(sub)\n        return inform(headID, subs, informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        self.output = 0\n        self.informTime = informTime\n        self.dic = dic = {}\n        for n, i in enumerate(manager):\n            if i not in dic: dic[i]=[]\n            dic[i].append(n)\n        \n        self.helper(headID, 0)\n        return self.output\n    \n    def helper(self, n, time):\n        self.output = max(self.output, time)\n        newtime = time + self.informTime[n]\n        for i in self.dic.get(n,[]):\n            self.helper(i, newtime)", "class Solution:\n\n    def numOfMinutes(self, n, headID, manager, informTime):\n        time_when_informed = {}\n        total = 0\n\n        time_when_informed[headID] = 0\n\n        def get_informed_time(node):\n            if node in time_when_informed:\n                return time_when_informed[node]\n            else:\n                ret = informTime[manager[node]] + get_informed_time(manager[node])\n                time_when_informed[node] = ret\n                return ret\n\n        ans = 0\n        for node in range(len(manager)):\n            ans = max(ans, get_informed_time(node))\n\n        return ans", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = {}\n        for i in range(n):\n            if i == headID:\n                continue\n            graph[manager[i]] = graph.get(manager[i], []) + [i]\n        \n        self.output = 0\n        def dfs(v, time):\n            # is leaf, \u7d50\u7b97 time\n            if v not in graph:\n                self.output = max(self.output, time)\n                return\n            \n            # for loop v's neighbor\n            for w in graph[v]:\n                dfs(w, time + informTime[v])\n        \n        dfs(headID, 0)\n        return self.output", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # using manager make graph => Value is key, Index is value, cost is informTime[Value]\n# do DFS find max\n        \n        graph = []\n        for i in range(n):\n            graph.append([])\n        for i in range(len(manager)):\n            if(manager[i]!=-1):\n                graph[manager[i]].append(i)\n        print(graph)\n        # DFS\n        stack =[(headID, 0)]\n        cost =0\n        maxi =0\n        while(len(stack)):\n            node, cost = stack.pop()\n            cost += informTime[node]\n            if(cost>maxi):\n                maxi = cost\n            for child in graph[node]:\n                stack.append((child, cost))\n        return maxi\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager_list = collections.defaultdict(list)\n        for i in range(len(manager)):\n            manager_list[manager[i]].append(i)\n        \n        queue = [(headID, informTime[headID])]\n        time = 0\n        while queue:\n            # print(queue)\n            cur, cur_time = queue.pop(0)\n            time = max(time, cur_time)\n            if manager_list[cur] != []:\n                print((cur, informTime[cur]))\n                employees = manager_list[cur]\n                manager_list[cur] = []\n                for employee in employees:\n                    queue.append((employee, cur_time + informTime[employee]))\n        return time\n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(node , curTime):\n            nonlocal totalTime\n            visited.add(node)\n            totalTime = max(curTime , totalTime)\n            for nextNode in graph[node]:\n                if nextNode not in visited:\n                    dfs(nextNode , curTime + informTime[node])\n        graph = defaultdict(set)\n        totalTime = 0\n        visited = set()\n        for u , v in enumerate(manager):\n            graph[u].add(v)\n            graph[v].add(u)\n        visited.add(-1)\n        dfs(headID , 0)\n        return totalTime\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = defaultdict(lambda: [])\n        for employee, m in enumerate(manager):\n          children[m].append(employee)\n          \n        def dfs(e, total_min):\n          cur_time = total_min + informTime[e] \n          if len(children[e]) == 0:\n            return cur_time\n          \n          max_time = cur_time\n          for employee in children[e]:\n            max_time = max(max_time, dfs(employee, cur_time))\n          return max_time\n            \n        return dfs(headID, 0)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def check(manager, informTime, total_time, cur):\n            if total_time[cur] >= 0:\n                return total_time[cur]\n            if manager[cur] == -1:\n                total_time[cur] = 0\n                return 0\n            boss = manager[cur]\n            total_time[cur] = check(manager, informTime, total_time, boss) + informTime[boss]\n            return total_time[cur]\n            \n        total_time = [-1]*n\n        rtv = 0\n        for i in range(n):\n            rtv = max(rtv, check(manager, informTime, total_time, i))\n        return rtv", "from collections import defaultdict\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        max_time_needed = 0\n        children = defaultdict(list)\n        for i, emp in enumerate(manager):\n            children[emp].append(i)\n            \n        stack = [(headID, informTime[headID])]\n        \n        while stack:\n            emp_id, time_taken = stack.pop()\n            max_time_needed = max(max_time_needed, time_taken)\n            \n            for ch in children[emp_id]:\n                stack.append((ch, time_taken + informTime[ch]))\n        \n        return max_time_needed", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        if n == 1:\n            return 0\n        \n        # need data structure to keep track of individual employees\n        time = collections.defaultdict(int)\n        \n        # do some preprocessing\n        # create a map worksUnder\n        # id -> {ids of employees that work under this manager}\n        worksUnder = collections.defaultdict(set)\n        \n        for i in range(n):\n            # employee i works under manager[i]\n            worksUnder[manager[i]].add(i)\n        \n        stack = [headID]\n        while stack:\n            managerID = stack.pop()\n            for i in worksUnder[managerID]:\n                    # employee i works under managerID\n                    # emplyee i's time is his manager's time plus \n                    # his manager's inform time\n                    time[i] = informTime[managerID] + time[managerID]\n                    stack.append(i)\n        \n        return max(time.values())", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        q = [(headID, 0)]\n        \n        graph = collections.defaultdict(list)\n        for i in range(n):\n            if manager[i] != -1:\n                graph[manager[i]].append(i)\n        \n        res = 0\n        \n        while q:\n            sz = len(q)\n            for _ in range(sz):\n                i,t = q.pop(0)\n                t += informTime[i]\n                res = max(res, t)\n                for j in graph[i]:\n                    q.append((j, t))\n        \n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for i in range(len(manager)):\n            if i == headID:\n                continue\n            graph[manager[i]].append(i)\n        time = 0\n        q = collections.deque([(headID, 0)])\n        while q:\n            node = q.popleft()\n            time = max(time, node[1])\n            for v in graph[node[0]]:\n                q.append((v, node[1] + informTime[node[0]]))\n        return time\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        max_time, time_map = 0, {}\n        \n        for curr in range(len(manager)):\n            \n            # memoization: backtracking to head or till the one we've\n            # already seen before\n            curr_em, curr_time = [], []\n            while curr not in time_map and curr != -1:\n                \n                curr_em.append(curr)\n                curr_time.append(informTime[curr])\n                curr = manager[curr]\n            \n            # reconstruct the accumulated pathsum, save it in the map\n            if curr_time:\n                rest_time = time_map[curr] if curr != -1 else 0\n                curr_time[-1] += rest_time\n                time_map[curr_em[-1]] = curr_time[-1]\n                for j in range(len(curr_time)-2, -1, -1):\n                    curr_time[j] = curr_time[j+1] + curr_time[j]\n                    time_map[curr_em[j]] = curr_time[j]\n                    \n                # compare every current longest pathsum with the currmax\n                max_time = max(max_time, curr_time[0])\n        return max_time", "class Node:\n    def __init__(self, val):\n        self.val = val\n        self.subordinates = []\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = [Node(t) for t in informTime]\n\n        root = None\n        for k, v in enumerate(manager):\n            if v >= 0:\n                nodes[v].subordinates.append(nodes[k])\n            else:\n                root = nodes[k]\n\n        ans = 0\n\n        def dfs(node, path):\n            nonlocal ans\n            if not node.subordinates:\n                ans = max(ans, path + node.val)\n                return\n            for n in node.subordinates:\n                dfs(n, n.val + path)\n\n        dfs(root, root.val)\n\n        return ans\n\n\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        tree = collections.defaultdict(list)\n        \n        for idx, val in enumerate(manager):\n            tree[val].append(idx)\n        \n        self.max_time = 0\n        def dfs(node):\n            time = 0\n            for child in tree[node]:\n                time = max(time, dfs(child))\n            return informTime[node] + time\n        \n        return dfs(headID)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        managerToReports, ms = defaultdict(set), set([headID])\n        for i, m in enumerate(manager): managerToReports[m].add(i)\n        def dfs(parent): return max([dfs(report) for report in managerToReports[parent]] or [0]) + informTime[parent]\n        return dfs(headID)", "class Solution:\n    # 1152 ms\n    def numOfMinutes(self, n, headID, manager, informTime):\n        @lru_cache(None)\n        def myTime(myBoss):\n            if manager[myBoss] > -1:\n                informTime[myBoss] += myTime(manager[myBoss])\n              #  t2 = \n                manager[myBoss] = -1\n               # return t1 + t2\n            return informTime[myBoss]\n        return max(map(myTime, manager))", "class Solution:\n    class AdjList:\n        def __init__(self, edges, h):\n            self.manager = edges\n            self.mlist = {}\n            for u, v in enumerate(edges):\n                \n                if v == -1:\n                    continue\n                if u not in self.mlist:\n                    self.mlist[u] = [v]\n                else:\n                    self.mlist[u].append(v)\n                \n                if v not in self.mlist:\n                    self.mlist[v] = [u]\n                else:\n                    self.mlist[v].append(u)\n            \n        def adjacent(self, node):\n            \n            if node not in self.mlist:\n                return []\n            \n            \n            return self.mlist[node]\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        adj = Solution.AdjList(manager, headID)\n        \n        visited = [0]*n\n        \n        \n        def dfs(node):\n            \n            visited[node] = 1\n            \n            \n            t = 0\n            for neig in adj.adjacent(node):\n                \n                if visited[neig] == 0:\n                    temp =  dfs(neig)\n                    t = max(t, temp)\n                    \n            return informTime[node] + t\n        \n        return dfs(headID)\n        \n        \n        \n        \n        \n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        n = len(manager)\n        graph = collections.defaultdict(list)\n        \n        for i in range(n):\n            graph[manager[i]].append(i)\n                \n        q = deque([(headID, 0)])\n        res = 0\n        \n        while q:\n            node, time = q.popleft()\n            res = max(res, time)\n            for nei in graph[node]:\n                q.append((nei, time + informTime[node]))\n        \n        return res\n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        adjList = defaultdict(list)\n\n        for i in range(n):\n            # manager[i] = j so j -> i\n            adjList[manager[i]].append(i)\n\n        # starting at headID - BFS traversal\n        queue = deque([(headID, 0)])\n\n        # total time to inform\n        maxTime = -1\n\n        # manager[headID] subordinates to the CEO\n        while queue:\n            current, currentTime = queue.pop()\n            # add all subordinates then add the time needed - repeat\n            maxTime = max(maxTime, currentTime + informTime[current] )\n\n            for employee in adjList[current]:\n                queue.appendleft((employee, currentTime + informTime[current]))\n\n\n        return maxTime", "class Node:\n    def __init__(self, val, weight=0):\n        self.root = val\n        self.weight = weight\n        self.children = []\n    \nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        hashmap = {}\n        \n        for i in range(n):\n            hashmap.update({i: Node(i)})\n        \n        for i, item in enumerate(manager):\n            if item == -1:\n                head = hashmap[i]\n            else:\n                hashmap[item].children.append(hashmap[i])\n        \n        for i, time in enumerate(informTime):\n            hashmap[i].weight = time\n            \n        def recur(root) -> int:\n            if not root.children:\n                return root.weight\n            \n            max_time = 0\n            for child in root.children:\n                time = recur(child)\n                if time > max_time:\n                    max_time = time\n            \n            return root.weight + max_time\n        \n        return recur(head)", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        companyTree = defaultdict(list)\n        \n        for idx, head in enumerate(manager):\n            if head != -1:\n                companyTree[head].append(idx)\n        # use heap \n        queue = deque([(headID, 0)])\n        visited = set()\n        res = 0\n        \n        while queue and len(visited) < n:\n            cur_employee, cur_total = queue.popleft()\n            res = max(res, cur_total + informTime[cur_employee])\n            # visited.add(cur_employee)\n            for subord in companyTree[cur_employee]:\n                # if subord not in visited: \n                queue.append((subord, cur_total + informTime[cur_employee]))\n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n#         dic = collections.defaultdict(list)\n#         for emp,mng in enumerate(manager):\n#             dic[mng].append([emp,informTime[mng]])\n\n#         bfs = [[headID,0]]\n#         ans = {}\n#         while(bfs):\n#             for i in range(len(bfs)):\n#                 cur_mng,time = bfs.pop(0)\n#                 ans[cur_mng] = time\n#                 bfs += [[x,y+time] for x,y in dic[cur_mng]]\n#         return max(ans.values())\n\n        g = collections.defaultdict(list)\n        for i, v in enumerate(manager):\n            g[v].append(i)\n        \n        def dfs(i):\n            return informTime[i] if not g[i] else max([informTime[i] + dfs(c) for c in g[i]])\n    \n        return dfs(headID)\n                \n    \n          #         0\n          #        / \\\\\n          #       1.  2\n          #     / \\\\. / \\\\\n          #    3  4. 5. 6\n          #   /\\\\  /\\\\ /\\\\   /\\\\\n          #  7  7 8 8 9 9 10 10\n        \n#         8\n#         0\n#         [-1,5,0,6,7,0,0,0]\n#         [89,0,0,0,0,523,241,519]\n        \n#                         0\n#                      / \\\\ \\\\ \\\\\n#                     2   5 6 7\n#                        / / /  \n#                       1 3 4\n                        \n    \n# 11\n# 4\n# [5,9,6,10,-1,8,9,1,9,3,4]\n# [0,213,0,253,686,170,975,0,261,309,337]\n\n\n#                          4         686\n#                           \\\\\n#                            10      337\n#                            /\n#                           3        253\n#                          /\n#                         9          309\n#                        /|\\\\\n#                       1 6 8        975\n#                      /  |  \\\\\n#                     7   2   5      170\n#                              \\\\\n#                               0    0\n", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        child_list = defaultdict(list)\n        for i in range(n):\n            j = manager[i]\n            if j >= 0:\n                child_list[j].append(i)\n        \n        def step(eid):\n            children = child_list[eid]\n            if not children:\n                return 0\n            \n            return informTime[eid] + max(step(cid) for cid in children)\n        \n        return step(headID)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        def dfs(node):\n            if manager[node] != -1:\n                informTime[node] += dfs(manager[node])\n                manager[node] = -1\n            return informTime[node]\n        return max(dfs(i) for i in range(n))\n", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        if not manager:\n            return 0\n        \n        #building the graph\n        graph = defaultdict(list)\n        for v in range(n):\n            graph[manager[v]].append(v)\n        \n        #For each node, we have to take the hieghest time\n        #returned from its subordinates/children\n        def dfs(node):\n            if node not in graph:\n                return informTime[node]\n            else:\n                return  informTime[node]+max([dfs(n) for n in graph[node]])\n        \n        return dfs(headID)\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        adj = {}\n        if len(manager) == 1:\n            return informTime[-1]\n        for i in range(n):\n            adj[i] = []\n            \n        for idx,i in enumerate(manager):\n            if i == -1:\n                continue\n            adj[i].append([idx,informTime[idx]])\n        # print(adj)    \n        ans = [-10**10]\n        def dfs(curr,cost):\n            # print(curr,cost)\n            ans[-1] = max(ans[-1],cost)\n            for i in range(len(adj[curr])):\n                # cost = adj[curr][i][1]\n                dfs(adj[curr][i][0],cost+adj[curr][i][1])\n            \n        dfs(headID,informTime[headID])\n        # print(adj)\n        return ans[-1]\n#         mx = -10**10\n#         for k,v in adj.items():\n#             for i in v:\n#                 mx = max(mx,i[1])\n#         return mx+informTime[headID]\n            \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph=collections.defaultdict(list)\n        for  i,c in enumerate(manager):\n            if c!=-1:\n                graph[c].append(i)\n   \n        \n        que=[(headID,0)]\n        ans=0\n        while que:\n            node,time=que.pop(0)\n            ans=max(ans,time)\n            for i in graph[node]:\n                que.append((i,time+informTime[node]))\n            \n            \n           \n          \n        return ans\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for idx in range(n):\n            graph[manager[idx]].append(idx)\n        \n        max_time = 0\n        queue = collections.deque([(headID, 0)])\n        while queue:\n            node, time = queue.popleft()\n            max_time = max(max_time, time)\n            for sub in graph[node]:\n                queue.append((sub, time + informTime[node]))\n        return max_time\n        \n            \n", "class Node:\n    \n    def __init__(self, unique_id, information_time):\n        self.information_time = information_time\n        self.unique_id = unique_id\n        self.childrens = []\n        \n    def add_child(self, child):\n        self.childrens.append(child)\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        root = Node(headID, informTime[headID]) # 0\n        id_node_mapping = {headID: root} # {0: (0, 0)}\n        \n        def dfs(node):\n            max_time = 0\n            for child in node.childrens:\n                max_time = max(dfs(child), max_time)\n                \n            return max_time + node.information_time\n        \n        for i, (parent, timetaken) in enumerate(zip(manager, informTime)):\n            \n            if i not in id_node_mapping:\n                id_node_mapping[i] = Node(i, timetaken)\n            else:\n                id_node_mapping[i].information_time = timetaken\n                \n            if parent not in id_node_mapping:\n                id_node_mapping[parent] = Node(parent, 0)\n                \n            id_node_mapping[parent].add_child(id_node_mapping[i])\n            \n        return dfs(root)\n", "class Node:\n    \n    def __init__(self, unique_id, information_time):\n        self.information_time = information_time\n        self.unique_id = unique_id\n        self.childrens = []\n        \n    def add_child(self, child):\n        self.childrens.append(child)\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        root = Node(headID, informTime[headID]) # 0\n        id_node_mapping = {headID: root} # {0: (0, 0)}\n        \n        def dfs(node):\n            max_time = 0\n            for child in node.childrens:\n                max_time = max(dfs(child), max_time)\n                \n            return max_time + node.information_time\n        \n        for i, (parent, timetaken) in enumerate(zip(manager, informTime)):\n            \n            if i == root.unique_id:\n                continue\n            \n            if i not in id_node_mapping:\n                id_node_mapping[i] = Node(i, timetaken)\n            else:\n                id_node_mapping[i].information_time = timetaken\n                \n            if parent not in id_node_mapping:\n                id_node_mapping[parent] = Node(parent, 0)\n                \n            id_node_mapping[parent].add_child(id_node_mapping[i])\n            \n        return dfs(root)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for i in range(n):\n            graph[manager[i]].append(i)\n            \n        queue = collections.deque([(headID, 0)])\n        result = 0\n        while queue:\n            i, time = queue.pop()\n            result = max(result, time)\n            for j in graph[i]:\n                queue.append((j, time + informTime[i]))\n        return result\n", "class Solution:\n    # 1152 ms\n    def numOfMinutes(self, n, headID, manager, informTime):\n        @lru_cache(None)\n        def myTime(myBoss):\n            if manager[myBoss] > -1:\n                t1 = informTime[myBoss]\n                t2 = myTime(manager[myBoss])\n                return t1 + t2\n            return informTime[headID]\n        return max(map(myTime, manager))", "class Tree:\n    def __init__(self):\n        pass\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = {}\n        \n        for i,val in enumerate(manager):\n            if val in graph:\n                graph[val].append(i)\n            else:\n                graph[val] = [i]\n        \n        ans = BFS(headID,informTime,graph)\n        return ans\n\ndef BFS(root,informTime,graph):\n        queue = [(root,0)]\n        maxTime = 0\n        \n        while(len(queue)):\n            currElem = queue.pop(0)\n            node = currElem[0]\n            currTime = currElem[1]\n            \n            CurrInformTime = informTime[node]\n            \n            timeToNext = currTime+CurrInformTime\n            maxTime = max(timeToNext,maxTime)\n                    \n            if node in graph:\n                children = graph[node]\n                for i in children:\n                    queue.append((i,timeToNext))\n        \n        return maxTime", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = defaultdict(list)\n        for i, j in enumerate(manager):\n            children[j].append(i)\n        \n        def dfs(node):\n            return informTime[node] + max([dfs(child) for child in children[node]] or [0])\n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        managerToReports, ms = defaultdict(set), set([headID])\n        for i, m in enumerate(manager): managerToReports[m].add(i)\n        self.result = 0\n        def dfs(parent, consumedTime):\n                if not managerToReports[parent]: self.result = max(self.result, consumedTime)\n                [dfs(report, consumedTime + informTime[parent]) for report in managerToReports[parent]]\n        dfs(headID, 0)\n        return self.result", "from collections import defaultdict, deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(mngr):\n            if not manager_map[mngr]:\n                return 0\n            result = 0\n            result += max(inform_time + dfs(subordinate) for subordinate, inform_time in manager_map[mngr])\n            return result\n        manager_map = defaultdict(list)\n        i = 0\n        for manager_ix, time in zip(manager, informTime):\n            manager_map[manager_ix].append((i, informTime[i]))\n            i += 1\n        \n        return dfs(-1)\n", "import heapq\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        \n        graph = collections.defaultdict(list)\n        for i in range(len(manager)):\n            u, v, w = manager[i], i, informTime[i]\n            if v == -1:\n                continue\n            graph[u].append((v, w))\n        \n        queue = [(headID, informTime[headID])]\n        seen = set()\n        heapq.heapify(queue)\n        time = {i: float('inf') for i in range(n)}\n        time[headID] = 0\n        \n        \n        while queue and len(seen) < n:\n            f, dist = heapq.heappop(queue)\n            seen.add(f)\n            time[f] = min(time[f], dist)\n            \n            for nb, w in graph[f]:\n                if nb not in seen:\n                    heapq.heappush(queue, (nb, dist + w))\n                    \n        \n        maxi = max(time.values())\n        \n        return maxi if maxi < float('inf') else -1\n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def method1():\n            def dfs(node,time):\n                nonlocal ans\n                if node not in set(manager):\n                    ans=max(ans,time)\n                    return\n                \n                for i,m in enumerate(manager):\n                    if m==node:\n                        dfs(i, time+informTime[m])\n                \n                        \n            ans=float('-inf')\n            dfs(headID,0)\n            return ans\n        #return method1()\n    \n        def method2():\n            children = [[] for i in range(n)]\n            for i, m in enumerate(manager):\n                if m >= 0: children[m].append(i)\n\n            def dfs(i):\n                return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n            return dfs(headID)\n        \n        return method2()", "from collections import defaultdict as dd\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        m_to_s = dd(set)\n        for i in range(len(manager)):\n            m_to_s[manager[i]].add(i)\n        stack = [(headID, 0)]\n        max_time = 0\n        while stack:\n            employee, time = stack.pop()\n            max_time = max(time, max_time)\n            for subordinate in m_to_s[employee]:\n                stack.append((subordinate, time + informTime[employee]))\n        return max_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def method1():\n            def dfs(node,time):\n                nonlocal ans\n                if not children[node]:\n                    ans=max(ans,time)\n                    return\n                \n                for c in children[node]:\n                    dfs(c, time+informTime[node])\n                \n            children = [[] for i in range(n)]\n            for i, m in enumerate(manager):\n                if m >= 0: children[m].append(i)\n                    \n            ans=float('-inf')\n            dfs(headID,0)\n            return ans\n        return method1()\n    \n        def method2():\n            children = [[] for i in range(n)]\n            for i, m in enumerate(manager):\n                if m >= 0: children[m].append(i)\n\n            def dfs(i):\n                return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n            return dfs(headID)\n        \n        return method2()", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        time = [-1] * n\n        time[headID] = 0\n        result = 0\n        \n        for i in range(n):\n            # if the index isn't visited (hasn't already been found with index=manager[index])\n            if time[i] == -1:\n                # search down a path\n                index = i\n                path = []\n                \n                # follows path of manager to subordinate\n                while time[index] == -1:\n                    path.append(index)\n                    index = manager[index]\n                \n                # adds everything together\n                for j in reversed(path):\n                    time[j] = time[manager[j]] + informTime[manager[j]]\n                    result = max(result, time[i])\n\n        return result", "class Node:\n    def __init__(self, id):\n        self.id = id\n        self.children = []\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = []\n        for i in range(n):\n            nodes.append(Node(i))\n        rootId = -1\n        for i in range(n):\n            if manager[i] != -1:\n                nodes[manager[i]].children.append(nodes[i])\n            else:\n                rootId = i\n        self.totalTime = 0\n        def dfs(root, time):\n            if not root:\n                return\n            self.totalTime = max(self.totalTime, time)\n            for node in root.children:\n                dfs(node, time + informTime[root.id])\n        dfs(nodes[rootId], 0)\n        return self.totalTime", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 1:\n            return informTime[0]\n        \n        s = collections.defaultdict(list)\n        for i in range(n):\n            if manager[i] == -1:\n                continue\n            s[manager[i]].append(i)\n        \n        return self.maxTime(s, informTime, headID)\n    \n        \n    def maxTime(self, employeeMap, informTime, curID):\n        if not employeeMap[curID]:\n            return informTime[curID]\n        \n        curMax = informTime[curID]\n        \n        for subordinate in employeeMap[curID]:\n            curMax = max(curMax, informTime[curID] + self.maxTime(employeeMap, informTime, subordinate))\n        \n        return curMax\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(node,cur_time):\n            nonlocal total_time\n            visited.add(node)\n            total_time = max(total_time,cur_time)\n            for next_node in graph[node]:\n                if next_node not in visited:\n                    dfs(next_node, cur_time + informTime[node])\n                    \n        \n        \n        \n        \n        total_time = 0\n        graph = defaultdict(set)\n        for u,v in enumerate(manager):\n            graph[u].add(v)\n            graph[v].add(u)\n        visited = set()\n        visited.add(-1)\n        \n        dfs(headID, 0)\n        return total_time\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = {}\n        for i,man in enumerate(manager):\n            if man == -1:\n                continue\n            if man not in subs:\n                subs[man] = set()# if man != -1 else None\n            subs[man].add(i)\n            \n        #print(subs)\n        queue = [(headID, 0, 0)]\n        informTimes = {}\n        \n        while queue:\n            curr, level, informedAt = queue.pop()\n            if curr not in subs:\n                continue\n            emps = subs[curr]\n                            \n            for e in emps:\n                if level not in informTimes:\n                    informTimes[level] = -1\n                currInformTime = informTime[curr] + informedAt\n                informTimes[level] = max(informTimes[level], currInformTime)\n                queue.append((e, level+1, currInformTime))\n        if not informTimes:\n            return 0\n        \n        maxInformTime = -1\n        for level, informTimesLevel in list(informTimes.items()):\n            maxInformTime = max(maxInformTime, informTimesLevel)\n        #maxLevel = max(informTimes.keys())\n        return maxInformTime\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def helper(emp):\n            if manager[emp]>=0:\n                informTime[emp]+=helper(manager[emp])\n                manager[emp]= -1\n            return informTime[emp]\n        return max(map(helper,manager))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = collections.defaultdict(list)\n        for i,a in enumerate(manager):\n            children[a].append(i)\n        def dfs(i):\n            if not children[i]:\n                return 0\n            else:\n                return informTime[i]+max(dfs(j) for j in children[i])\n        return dfs(children[-1][0])\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(g, u, informTime, time):\n            total_time = time\n            for v in g[u]:\n                if v != -1: total_time = max(total_time, dfs(g, v, informTime, time + informTime[v]))\n                \n            return total_time\n        \n        \n        g = defaultdict(list)\n        for i, m in enumerate(manager):\n            if m != -1: g[m].append(i)\n        \n        return dfs(g, headID, informTime, informTime[headID])\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # ret[i] is num minutes from start until employee i knows about it\n        ret = [-1]*n\n        def computeFor(i):\n            mana = manager[i]\n            if mana == -1:\n                #is head of company\n                return 0\n            # otherwise manager needs to learn, then informTime\n            return getVal(mana) + informTime[mana]\n        \n        def getVal(i):\n            # cached computation\n            if ret[i] == -1:\n                ret[i] = computeFor(i)\n            return ret[i]\n        \n        return max(getVal(i) for i in range(n))\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 1:\n            return 0\n        t = 0\n        m = {}\n        start = None\n        for i in range(len(manager)):\n            if manager[i] != -1:\n                if manager[i] in m:\n                    m[ manager[i] ].append( i )\n                else:\n                    m[ manager[i] ] = [ i ]\n            else:\n                start = i\n        q = []\n        q.append((start,informTime[start]))\n        hi = 0 # max value\n        while (len(q) > 0):\n            # print(q)\n            out = q.pop(0)\n            index = out[0]\n            cost = out[1]\n            if cost > hi: hi = cost\n            if index in m:\n                for i in m[index]:\n                    q.append((i, cost + informTime[i]))\n        \n        return hi", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        for person, manag in enumerate(manager):\n            if manag!=-1:\n                children[manag].append(person)\n        \n        def dfs(node):\n            return max((dfs(child) for child in children[node]),default=0)+informTime[node]\n        return dfs(headID)\n        \n", "class Solution:\n    def __init__(self):\n        self.result = -1\n        self.reports_map = defaultdict(list)\n        \n    def notifyReport(self, managerID: int, timeSpent: int, informTime: List[int]):\n        if managerID not in self.reports_map:\n            if self.result == -1 or timeSpent > self.result:\n                self.result = timeSpent\n        else:\n            for report in self.reports_map[managerID]:\n                self.notifyReport(report, timeSpent + informTime[managerID], informTime)\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        for i in range(0, len(manager)):\n            self.reports_map[manager[i]].append(i)\n        \n        self.notifyReport(headID, 0, informTime)\n        \n        return self.result", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        graph = defaultdict(list)\n        for i, mgr in enumerate(manager):\n            graph[mgr].append(i)\n        \n        q = deque()\n        q.append((-1, 0))\n        seen = set([-1])\n        ans = 0\n        \n        while q:\n            node, cumSum = q.popleft()\n            ans = max(ans, cumSum)\n            for sub in graph[node]:\n                if sub not in seen:\n                    seen.add(sub)\n                    q.append((sub, cumSum+informTime[sub]))\n        return ans\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(node):\n            return max([dfs(j) for j in tree[node]] or [0]) + informTime[node]\n        ret=[0]\n        tree = defaultdict(set)\n        for i, m in enumerate(manager):\n            tree[m].add(i)\n        return dfs(headID)", "class Solution:\n    class Node :\n        def __init__(self, val, inform = 0) :\n            self.val = val\n            self.inform = inform\n            self.children = []\n    \n    def traversal(self, root, time) -> int :\n      if not root or root is None : return time\n      final_time = time\n      # print(root.val, root.children)\n      for node in root.children :\n        final_time = max(final_time, self.traversal(node, time + root.inform))\n      return final_time\n      \n      \n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        d = {}\n        root = self.Node(headID)\n        d[headID] = root\n        \n        for i in range(n) :\n          if i == headID :\n            d[headID].inform = informTime[i]\n            continue\n          d[i] = self.Node(i, informTime[i])\n          \n        for i,m in enumerate(manager) :\n          if m == -1 : continue\n          d[m].children.append(d[i])  # add reportees\n#         for k,v in d.items() :\n#           print(k, v.val, len(v.children))\n        \n        \n        final_time = self.traversal(root, 0)\n        return final_time\n        \n          \n        \n          \n", "class Solution:\n    def dfsFromId(self, g, visited, informTime, vertex, times, currTime):\n        visited[vertex] = True\n        times[0] = max(times[0], currTime)\n        for to in g[vertex]:\n            if not visited[to]:\n                self.dfsFromId(g, visited, informTime, to, times, currTime + informTime[vertex])\n        \n        \n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        g = [set() for i in range(n)]\n        visited = [False] * n\n        maxMinutes = [0]\n        \n        for i,v in enumerate(manager): g[v].add(i)\n            \n        self.dfsFromId(g, visited, informTime, headID, maxMinutes, 0)\n                \n        return maxMinutes[0]", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager_sub = defaultdict(list)\n        for e, m in enumerate(manager):\n            manager_sub[m].append(e)\n        \n        res = 0\n        def max_inform_time(employee, initial_time):\n            subordinate_time = []\n            \n            for e in manager_sub[employee]:\n                t = max_inform_time(e, initial_time + informTime[e])\n                subordinate_time.append(t)\n            \n            return max(subordinate_time) if subordinate_time else initial_time\n\n        return max_inform_time(headID, informTime[headID])\n    \n", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        \n        return max(list(map(dfs, list(range(n)))))\n", "from collections import *\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        mapper = defaultdict(list)\n        for i, man in enumerate(manager):\n            mapper[man].append(i)\n        queue = [(headID,informTime[headID])]\n        vis = set()\n        ans = 0\n        while queue:\n            iden, time = queue.pop(0)\n            ans = max(ans,time)\n            vis.add(iden)\n            for sub in mapper[iden]:\n                if sub not in vis:\n                    queue.append((sub, time + informTime[sub]))\n        return ans", "from collections import deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        graph = {}\n        \n        if len(manager) == 1:\n            return 0\n        \n        for emp,manager in enumerate(manager):\n            if emp == headID:\n                continue\n            if manager in graph:\n                graph[manager].append(emp)\n            else:\n                graph[manager] = [emp]\n                \n        ans = {}\n        \n        ans[headID] = 0\n        \n        Queue = deque()\n        Queue.append(headID)\n        \n        maxTime = 0\n        while Queue:\n            man = Queue.popleft()  \n            if man not in graph:\n                continue\n            for emp in graph[man]:\n                ans[emp] = ans[man] + informTime[man]\n                maxTime = max(maxTime, ans[emp])\n                Queue.append(emp)\n                \n        return maxTime", "from collections import deque\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        class TreeNode():\n            def __init__(self, time=0):\n                self.children = []\n                self.time = time\n\n        tree_nodes = [None for _ in range(n)]\n        for index in range(n):\n            # Set up child\n            if tree_nodes[index] is None:\n                tree_nodes[index] = TreeNode(time=informTime[index])\n                \n            # Set up parent\n            if manager[index] != -1:\n                if tree_nodes[manager[index]] is None:\n                    tree_nodes[manager[index]] = TreeNode(time=informTime[manager[index]])\n\n                tree_nodes[manager[index]].children.append(index)\n                \n            \n        def BFS(root: TreeNode) -> int:\n            longest_time = 0\n            queue = deque()\n            queue.append(root)\n            \n            while len(queue):\n                node = queue.popleft()\n                \n                longest_time = max(longest_time, node.time)\n                \n                for child in node.children:\n                    tree_nodes[child].time += node.time\n                    queue.append(tree_nodes[child])\n                    \n            return longest_time\n        \n        return BFS(tree_nodes[headID])\n            \n        ##############################\n        \n        def sum_leaf_to_root(leaf: int) -> int:\n            if leaf == headID:\n                return informTime[headID]\n            \n            boss = manager[leaf]\n            total_time = 0\n            \n            while boss != headID:\n                total_time += informTime[boss]\n                boss = manager[boss]\n                \n            total_time += informTime[headID]\n            \n            return total_time\n        \n        return max(\n            sum_leaf_to_root(leaf)\n            for leaf in (\n                index\n                for index in range(len(manager))\n                if index not in manager\n            )\n        )", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        sub_h = {}\n        for idx in range(n):\n            if idx==headID: continue\n            if manager[idx] not in sub_h: sub_h[manager[idx]] = [informTime[manager[idx]], idx]\n            else: sub_h[manager[idx]].append(idx)\n        self.res = 0\n        \n        def helper(cur, t):\n            if cur not in sub_h: \n                self.res = max(self.res, t)\n                return\n            for sub in sub_h[cur][1:]:\n                helper(sub, t+sub_h[cur][0])\n                \n        helper(headID, 0)\n        return self.res\n        \n\n", "class Solution:\n    def numOfMinutes(self, n, headID, manager, informTime):\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(dfs(i) for i in range(n))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        org = collections.defaultdict(list)\n        self.res = 0\n        \n        for i, v in enumerate(manager):\n            org[v].append(i)\n        \n        def dfs(manager, time):\n            self.res = max(self.res, time)\n            for sub in org[manager]:\n                dfs(sub, time + informTime[sub])\n        \n        dfs(headID, informTime[headID])\n        return self.res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        stack = [(headID, 0)]\n        \n        ans = 0\n        dic = {}\n        for e, m in enumerate(manager):\n            dic[m] = dic.get(m, set())\n            dic[m].add(e)\n        while stack:\n            em, time = stack.pop(0)\n            if informTime[em] == 0:\n                ans = max(ans, time)\n            else:\n                for e in dic.get(em, []):\n                    stack.append((e, informTime[em]+ time))\n        return ans\n            \n        \n        \n        \n        ##O(n), O(n)\u4e24\u79cd\u65b9\u6cd5\n        \n        \n        \n        \n        \n#         manage = {}\n#         for i in range(n):\n#             manage[manager[i]] = manage.get(manager[i], []) + [i]\n            \n#         ans = 0\n#         stack = [(headID,0)]\n\n#         while stack:\n#             node, time = stack.pop()\n#             if informTime[node] == 0:\n#                 ans = max(ans, time)\n#             else:\n#                 for nei in manage[node]:\n#                     stack.append((nei, informTime[node] + time))\n            \n#         return ans\n", "class Solution:\n    # 1152 ms\n    def numOfMinutes(self, n, headID, manager, informTime):\n       # @lru_cache(None)\n        def myTime(myBoss):\n            if manager[myBoss] > -1:\n                informTime[myBoss] += myTime(manager[myBoss])\n              #  t2 = \n                manager[myBoss] = -1\n               # return t1 + t2\n            return informTime[myBoss]\n        return max(map(myTime, manager))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        \n        employeesDict = {}\n        \n        for i in range(0, len(manager)): \n            \n            if manager[i] == -1: \n                continue\n            \n            if manager[i] in employeesDict: \n                employeesDict[manager[i]].append(i)\n            else:\n                l = []\n                l.append(i)\n                employeesDict[manager[i]] = l\n\n    \n        return self.helper(headID, informTime[headID], employeesDict, informTime)\n    \n    \n    def helper(self, currEmp, currTime, employeesDict, informTime):\n\n        if currEmp not in employeesDict: \n            return currTime\n        newTime = -1\n        managerList = employeesDict[currEmp]\n        for i in range(0, len(managerList)):\n\n            newTime = max(newTime, self.helper(managerList[i], informTime[managerList[i]], employeesDict, informTime) + currTime)\n\n        return newTime\n\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = {}\n        for i,man in enumerate(manager):\n            if man == -1:\n                continue\n            if man not in subs:\n                subs[man] = set()# if man != -1 else None\n            subs[man].add(i)\n            \n        #print(subs)\n        queue = [(headID, 0, 0)]\n        informTimes = {}\n        \n        while queue:\n            curr, level, informedAt = queue.pop()\n            if curr not in subs:\n                continue\n            emps = subs[curr]\n                            \n            for e in emps:\n                if level not in informTimes:\n                    informTimes[level] = -1\n                currInformTime = informTime[curr] + informedAt\n                informTimes[level] = max(informTimes[level], currInformTime)\n                queue.append((e, level+1, currInformTime))\n        if not informTimes:\n            return 0\n        \n        return max(informTimes.values())\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        tree = collections.defaultdict(list)\n        \n        for idx, val in enumerate(manager):\n            tree[val].append(idx)\n        \n        self.max_time = 0\n        def dfs(node, time):\n            new_time = time + informTime[node]\n            self.max_time = max(self.max_time, new_time)\n            for child in tree[node]:\n                dfs(child, new_time)\n        dfs(headID, 0)\n        return self.max_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        adj = defaultdict(list)\n        \n        for i in range(n):\n            adj[manager[i]].append(i)\n\n        def dfs(n: int) -> int:\n            return informTime[n] + max([dfs(nn) for nn in adj[n]] or [0])\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        self.employee = collections.defaultdict(list)\n        self.time = 0\n        self.infromTime = informTime\n        \n        for i, m in enumerate(manager):\n            self.employee[m].append(i)\n        \n        self.dfs(headID, informTime[headID])\n        \n        return self.time\n        \n    def dfs(self, rootID, time):\n        self.time = max(time, self.time)\n        \n        for employee in self.employee[rootID]:\n            self.dfs(employee, time+self.infromTime[employee])", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def helper(i, manager, informTime):\n            if manager[i] != -1:\n                informTime[i] += helper(manager[i], manager, informTime)\n                manager[i] = -1\n            return informTime[i]\n            \n        res = 0\n        for i in range(n):\n            res = max(res, helper(i, manager, informTime))\n        return res", "class Node:\n    def __init__(self,id,time):\n        self.id = id\n        self.informTime = time\n        self.children = set()\n        \nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = [Node(x,informTime[x]) for x in range(n)]\n        for i,v in enumerate(manager):\n            if v == -1:continue\n            nodes[v].children.add(nodes[i])        \n            \n        def recursive(node):\n            if not node:return 0\n            temp = 0\n            for n in node.children:\n                temp = max(temp,recursive(n))\n            return temp+node.informTime\n        \n        return recursive(nodes[headID])\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        reports = collections.defaultdict(list)\n        for i, m in enumerate(manager):\n            reports[m].append(i)\n        \n        def dfs(i):\n            return informTime[i] + max([dfs(r) for r in reports[i]], default=0) \n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        inputs = {i:0 for i in range(n)}\n        graph = {i: set() for i in range(n)}\n        for i, m in enumerate(manager):\n            # edge m --> i\n            if m == -1: continue\n            if i not in graph[m]:\n                graph[m].add(i)\n                inputs[i] += 1\n                \n        stack = [(headID, 0)]\n        ans = 0\n        while stack:\n            i, elapsed = stack.pop()\n            ans = max(ans, elapsed)\n            # find all subordinates of i\n            new_elapsed = elapsed + informTime[i]\n            for nb in graph[i]: \n                inputs[nb] -= 1\n                if inputs[nb] == 0:\n                    stack.append((nb, new_elapsed))\n                    \n        return ans\n                    \n                \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i]!=-1:\n                informTime[i]+=dfs(manager[i])\n                manager[i]=-1\n            return informTime[i]\n        return max(map(dfs,range(n)))          ", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        time = [-1 for _ in range(n)]\n        time[headID] = 0\n        result = 0\n        for i in range(n):\n            index = i\n            path = []\n            while time[index] == -1:\n                path.append(index)\n                index = manager[index]\n            for employee in reversed(path):\n                #print(\\\"employee: {}, manager: {}, time of manager: {}, informTime of manager: {}\\\".format(employee, manager[employee],  time[manager[employee]], informTime[manager[employee]]))\n                time[employee] = time[manager[employee]] + informTime[manager[employee]]\n            result = max(result, time[i])\n        print(time)\n        return result            \n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = {}\n        for i,man in enumerate(manager):\n            if man == -1:\n                continue\n            if man not in subs:\n                subs[man] = set()\n            subs[man].add(i)\n            \n        queue = [(headID, 0)]\n        maxInformTime = 0\n        \n        while queue:\n            curr,informedAt = queue.pop()\n            if curr not in subs:\n                continue\n                \n            currInformTime = informTime[curr] + informedAt\n            maxInformTime = max(maxInformTime, currInformTime)\n            emps = subs[curr]  \n            for e in emps:\n                queue.append((e,currInformTime))\n                \n        return maxInformTime\n", "class RelationTree:\n    def __init__(self, e_id, time):\n        self.e_id = e_id\n        self.time = time\n        self.subs = []\n        \n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        relation_dict = collections.defaultdict(list)\n        for i, m_id in enumerate(manager):\n            relation_dict[m_id].append(i)\n        self.max_time = 0\n        def createTree(e_id, cum_time):\n            curr_root = RelationTree(e_id, informTime[e_id])\n            if curr_root.time:\n                for sub_id in relation_dict[e_id]:\n                    curr_root.subs.append(createTree(sub_id, cum_time + curr_root.time))\n            else:\n                self.max_time = max(self.max_time, cum_time)\n            return curr_root\n        root = createTree(headID, 0)\n        \n        return self.max_time\n        \n        \n", "class Node:\n    def __init__(self, id, informTime=0):\n        self.id = id\n        self.employees = []\n        self.informTime = informTime\n\nclass Solution:\n    def construct_tree(self, headID, managers, informTime):\n        manager_to_employees = {}\n        for employee, manager in enumerate(managers):\n            if manager in manager_to_employees:\n                manager_to_employees[manager].append(employee)\n            else:\n                manager_to_employees[manager] = [employee]\n        \n        root = Node(headID, informTime[headID])\n        stack = [root]\n        while stack:\n            node = stack.pop()\n            if node.id not in manager_to_employees:\n                continue\n            for employee in manager_to_employees[node.id]:\n                next_node = Node(employee, informTime[employee])\n                node.employees.append(next_node)\n                stack.append(next_node)\n        return root\n\n    def shortest_informTime(self, root): \n        max_time = 0\n        if root and root.employees:\n            for employee in root.employees:\n                max_time= max(max_time, self.shortest_informTime(employee))\n            max_time += root.informTime\n        return max_time\n\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        root = self.construct_tree(headID, manager, informTime)\n        return self.shortest_informTime(root)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        #DFS\n        \n        subordinates = collections.defaultdict(list)\n        \n        for i, m in enumerate(manager):\n            \n            if i != headID:\n                subordinates.setdefault(m,[]).append(i)\n                #subordinates[m].append(i)\n                \n        self.res = 0\n        \n        \n        def dfs(manager, time):\n            \n            self.res = max(self.res, time)\n            \n            for subordinate in subordinates[manager]:\n                \n                dfs(subordinate, time + informTime[manager])\n                \n        dfs(headID, 0) \n        \n        return self.res\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinates = collections.defaultdict(list)\n        for i in range(n):\n            subordinates[manager[i]].append(i)\n    \n        queue = collections.deque([(headID, 0)])\n        max_time = 0\n        while queue:\n            employee_mgr, time = queue.popleft()\n            max_time = max(max_time, time)\n            queue.extend((employee, time + informTime[employee_mgr]) for employee in subordinates[employee_mgr])\n        \n        return max_time", "class Solution:\n    ans = 0\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # Time Limit Exceeded\n        d = {}\n        totalTime = [-1]*n\n        def help(index):\n            if index == headID:\n                d[index] = 0\n                return 0\n            else:\n                m = manager[index]\n                cost = 0\n                if m in d:\n                    cost = informTime[m] + d[m]\n                else:\n                    cost = informTime[m] + help(m)\n                d[index]=cost\n                totalTime[index] = cost\n                self.ans = max(self.ans,cost)\n                return cost\n        for i in range(n):\n            if totalTime[i] <0:\n                help(i)\n        return self.ans\n        \n", "class Node:\n    def __init__(self, time):\n        self.time = time\n        self.children = []\n\ndef dfs(node):\n    res = node.time\n    if node.children:\n        res += max(dfs(c) for c in node.children)\n    return res\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = [Node(t) for t in informTime]\n        for i in range(n):\n            if i == headID:\n                continue\n            nodes[manager[i]].children.append(nodes[i])\n        return dfs(nodes[headID])", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        \n        \n        # my solution ... 1744 ms ... 48 % ... 68.7 MB ... 0 %\n        #  time: O(n)\n        # space: O(n)\n        \n        def func(parent, t):\n            self.res = max(self.res, t)\n            for child in subs[parent]:\n                func(child, t + informTime[parent])\n        \n        subs = collections.defaultdict(set)\n        for i,m in enumerate(manager):\n            if m != -1:\n                subs[m].add(i)\n        self.res = 0\n        func(headID, 0)\n        return self.res\n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        total_time = [0] * n\n        total_time[headID] = informTime[headID]\n        for i in range(n):\n            if total_time[i] == 0:\n                path = [i]\n                c_id = manager[i]\n                while c_id != -1 and total_time[c_id] == 0:\n                    path.append(c_id)\n                    c_id = manager[c_id]\n                c_time = total_time[c_id]\n                if len(path) > 0:\n                    total_time[path[-1]] = informTime[path[-1]] + c_time\n                    for j in range(len(path)-2, -1, -1):\n                        total_time[path[j]] = informTime[path[j]] + total_time[path[j+1]]\n        return max(total_time)\n                    \n", "class TreeNode:\n    def __init__(self, val, children):\n        self.val = val\n        self.children = children\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        people = []\n        for time in informTime:\n            people.append(TreeNode(time, []))\n        for ID, man in enumerate(manager):\n            if man != -1:\n                people[man].children.append(people[ID])\n        def dfs(node):\n            return node.val + max(dfs(child) for child in node.children) if node.children else 0\n        return dfs(people[headID])\n        \n", "class Solution:\n    def dfs(self,headId,employee,informTime):\n        maxTime = 0\n        \n        for e in employee[headId]:\n            maxTime = max(maxTime,self.dfs(e,employee,informTime) + informTime[headId])\n            \n        return maxTime\n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        employee = [[0 for i in range(0)] for j in range(n)]\n        \n        for i in range(n):\n            if manager[i] != -1:\n                employee[manager[i]].append(i)\n            \n        return self.dfs(headID,employee,informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = {}\n        for i,man in enumerate(manager):\n            if man == -1:\n                continue\n            if man not in subs:\n                subs[man] = set()\n            subs[man].add(i)\n            \n        queue = [(headID, 0)]\n        maxInformTime = 0\n        \n        while queue:\n            curr,informedAt = queue.pop()\n            if curr not in subs:\n                continue\n                \n            emps = subs[curr]  \n            for e in emps:\n                currInformTime = informTime[curr] + informedAt\n                maxInformTime = max(maxInformTime, currInformTime)\n                queue.append((e,currInformTime))\n                \n        return maxInformTime\n", "from collections import deque\n\n\nclass Node:\n    def __init__(self, id: int, inform_t: int):\n        self.id = id\n        self.children = []\n        self.inform_t = inform_t\n    \n    def __repr__(self):\n        return f'<{self.id} ({self.inform_t}): {len(self.children)}>'\n    \n    def total_inform_time(self):\n        t = self.inform_t\n        if self.children:\n            t += max(ch.total_inform_time() for ch in self.children)\n        return t\n\nclass Solution:\n    \n    def build_tree(self, manager: List[int], inform_time: List[int]) -> Node:\n        nodes = [None] * len(manager)\n        root = None\n        for id, man_id in enumerate(manager):\n            if nodes[id] is None:\n                nodes[id] = Node(id, inform_time[id])\n            \n            if man_id >= 0:\n                if nodes[man_id] is None:\n                    nodes[man_id] = Node(man_id, inform_time[man_id])\n\n                nodes[man_id].children.append(nodes[id])\n            else:\n                root = nodes[id]\n        return root\n    \n    \n    def numOfMinutes(self, n: int, head_id: int, manager: List[int], inform_time: List[int]) -> int:\n        root = self.build_tree(manager, inform_time)\n        return root.total_inform_time()\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        #Step1: build the graph\n        adjList = collections.defaultdict(list)\n        for i, (u, v) in enumerate(zip(manager, informTime)):\n            adjList[u].append((i, v))\n        #Step2: dfs with stack\n        stack = adjList[-1]\n        res = 0\n        while stack:\n            u, v = stack.pop()\n            res = max(res, v)\n            for nu, nv in adjList[u]:\n                stack.append((nu, v + nv))\n        return res\n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        employee_to_manager = collections.defaultdict(list)\n        \n        for i in range(len(manager)):\n            employee_to_manager[manager[i]].append(i)\n        queue = collections.deque()\n        queue.append((headID, informTime[headID]))\n        \n        total_time = 0\n        \n        while queue:\n            manager, t = queue.popleft()\n            \n            total_time = max(total_time, t)\n            \n            for employee in employee_to_manager[manager]:\n                queue.append((employee, t +  informTime[employee]))\n        return total_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        if n == 1:\n            return 0 \n\n        graph = defaultdict(list)\n\n        for idx, manager in enumerate(manager):\n            graph[manager].append((informTime[manager], idx))\n        \n\n        pQueue = [(0, headID)]\n        maxTime = 0 \n\n        while pQueue:\n            \n            currTime , currId = heapq.heappop(pQueue)\n            maxTime = max(maxTime, currTime)\n            \n            for nextTime, nei in graph[currId]:\n                heapq.heappush(pQueue, (currTime + nextTime, nei))\n\n        return maxTime", "from collections import defaultdict\nclass Solution:\n    # time for a manager = time[employee] + time[manager]\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # [manager1, manager2...]\n        # 0th employee, 1st employee\n        mp = defaultdict(list) # {manager: [employee id]}\n        for i in range(n):\n            if manager[i] != -1:\n                mp[manager[i]].append(i)\n        \n        def find_time(manager):\n            employees = mp[manager]\n            maxval = 0\n            for employee in employees:\n                maxval = max(maxval, find_time(employee))\n            return maxval + informTime[manager]\n        \n        return find_time(headID)\n            \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        q = [[headID, informTime[headID]]]\n        d = defaultdict(list)\n        for i, val in enumerate(manager):\n            d[val].append(i)\n        res = 0\n        while True:\n            new_q = []\n            cur_max_time = 0\n            while q:\n                index, time = q.pop()\n                res = max(res, time)\n                for v in d[index]:\n                    new_q.append((v, time+informTime[v]))\n            q = new_q[:]\n            \n            if not q:\n                break\n        return res", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        '''\n        \n        if not manager:\n            return 0\n        \n        #building the graph\n        graph = defaultdict(list)\n        for v in range(n):\n            graph[manager[v]].append(v)\n        \n        #For each node, we have to take the hieghest time\n        #returned from its subordinates/children\n        def dfs(node):\n            if node not in graph:\n                return informTime[node]\n            else:\n                return  informTime[node]+max(map(lambda n: dfs(n), graph[node]))\n        \n        return dfs(headID)\n        '''\n        \n        if not manager: return 0\n        g = collections.defaultdict(list)\n        for e, m in enumerate(manager):\n            g[m].append(e)\n        \n        def dfs(u):\n            if u not in g: return 0\n            return informTime[u]+max(dfs(v) for v in g[u])\n        \n        return dfs(headID)\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        pass\n        \n        \n        \n        def helper(i):\n            if i not in g:\n                return 0\n            \n            children = g[i]\n            nchild = len(children)\n            res = 0\n            for j in range(nchild):\n                v = children[j]\n                res = max(res,helper(v))\n            return res + informTime[i]\n                \n                \n        \n        g = {}\n        \n        n = len(manager)\n        for i in range(n):\n            themanager = manager[i]\n            if themanager == -1:\n                continue\n            if themanager not in g:\n                g[themanager] = []\n                \n            g[themanager].append(i)\n            \n        return helper(headID)\n", "class Solution:\n    def numMin(self, n: int, headID: int, subordinates: List[int], informTime: List[int]) -> int:\n        if subordinates[headID] == []:\n            return 0\n        else:\n            return informTime[headID] + max(self.numMin(n, e, subordinates, informTime) for e in subordinates[headID])\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinates = [[] for x in range(n)]\n        for i, m in enumerate(manager):\n            if m != -1:\n                subordinates[m].append(i)\n        print(subordinates)\n        return self.numMin(n, headID, subordinates, informTime)\n", "import heapq\n\nclass Solution:\n    def numOfMinutes(self, N: int, H: int, M: List[int], T: List[int]) -> int:\n        graph = defaultdict(lambda:[])\n        for i, m in enumerate(M):\n            if i != H:\n                graph[m].append(i)\n\n        cnt = 0; heap = []\n        heapq.heappush(heap, (T[H], H))\n        while heap:\n            cur = heapq.heappop(heap)\n            cnt += 1\n            if cnt == N:\n                return cur[0]\n            if cur[1] in graph:\n                for sub in graph[cur[1]]:\n                    heapq.heappush(heap, (T[sub]+cur[0], sub))\n\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        man_idx = [[man, idx] for idx, man in enumerate(manager)]\n        man_copy = [[man, idx] for idx, man in enumerate(manager)]\n        max_time = 0\n        curr_time = 0\n        memo_table = {}\n        start = man_idx[-1][1]\n        while man_idx:\n            curr_man = man_idx.pop()\n            if curr_man[1] in memo_table:\n                curr_time += memo_table[curr_man[1]]\n                memo_table[start] = curr_time\n                max_time = max(max_time, curr_time)\n                if len(man_idx) > 0:\n                    start = man_idx[-1][1]\n                curr_time = 0\n                continue\n            curr_time += informTime[curr_man[1]]\n            if curr_man[0] == -1:\n                max_time = max(max_time, curr_time)\n                memo_table[start] = curr_time\n                if len(man_idx) > 0:\n                    start = man_idx[-1][1]\n                curr_time = 0\n            else:\n                man_idx.append(man_copy[curr_man[0]])\n        return max_time\n", "import sys\n\nsys.setrecursionlimit(10**6) \n\nclass TreeNode:\n    def __init__(self, val):\n        self.val = val\n        self.par = None\n        self.kids = []\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        nodes = [TreeNode(informTime[emp]) for emp in range(n)]\n        for emp in range(n):\n            if manager[emp] != -1:\n                nodes[emp].par = nodes[manager[emp]]\n                nodes[manager[emp]].kids.append(nodes[emp])\n        \n        head = nodes[headID]\n        \n        def helper(node):\n            return node.val + max([helper(k) for k in node.kids],default=0)\n        \n        return helper(head)", "from typing import List\n\n\nclass TreeNode(object):\n    def __init__(self, val: int):\n        self.val = val\n        self.children = []\n\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # construct tree\n        tree_map = {headID: TreeNode(headID)}\n        for i in range(n):\n            if i == headID:\n                continue\n            if i not in tree_map:\n                tree_map[i] = TreeNode(i)\n            if manager[i] not in tree_map:\n                tree_map[manager[i]] = TreeNode(manager[i])\n            tree_map[manager[i]].children.append(i)\n\n        # level order\n        res = 0\n        root = tree_map[headID]\n        queue = [(root, 0)]\n        while len(queue) > 0:\n            r, s = queue.pop(0)\n            if len(r.children) == 0:\n                res = max(res, s)\n            for c in r.children:\n                queue.append((tree_map[c], s + informTime[r.val]))\n        return res", "import collections\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for i in range(len(manager)):\n            if manager[i] != -1:\n                graph[manager[i]].append(i)\n        queue = [(headID, 0)]\n        ans = 0\n        while queue:\n            m, val = queue.pop(0)\n            ans = max(ans, val)\n            for w in graph[m]:\n                queue.append((w, val+informTime[m]))\n        return ans\n                        \n", "class Solution: \n\n    def processEmployee(self, employee, managerOfEmployee, informTime, dp):\n        if employee == -1 or dp[employee]: return employee\n        dp[employee] = 1\n        managerOfEmployee[employee] = self.processEmployee(managerOfEmployee[employee], managerOfEmployee, informTime, dp)\n        if managerOfEmployee[employee] != -1: informTime[employee] += informTime[managerOfEmployee[employee]]\n        return employee\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        dp = [0] * (n + 1)\n        for employee in range(n): self.processEmployee(employee, manager, informTime, dp)                          \n        return max(informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i,t):\n            if i not in dic: self.ans = max(self.ans,t)\n            for a,b in dic[i]:\n                dfs(a,t+b)\n        dic,self.ans = defaultdict(list),0\n        for i,m in enumerate(manager): dic[m].append((i,informTime[i]))\n        dfs(dic[-1][0][0],dic[-1][0][1])\n        return self.ans\n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subord = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0:\n                subord[m].append(i)\n                \n        return self.dfs(headID, subord, informTime)\n        \n    def dfs(self, i, subord, informTime):\n        return max([self.dfs(e, subord, informTime) for e in subord[i]] or [0]) + informTime[i]", "class Solution:\n    def numMin(self, total_time, n: int, headID: int, subordinates: List[int], informTime: List[int]) -> int:\n        if subordinates[headID] == []:\n            return total_time\n        else:\n            return max(self.numMin(informTime[headID] + total_time, n, e, subordinates, informTime) for e in subordinates[headID])\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinates = [[] for x in range(n)]\n        for i, m in enumerate(manager):\n            if m != -1:\n                subordinates[m].append(i)\n        print(subordinates)\n        return self.numMin(0, n, headID, subordinates, informTime)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        manager2employee = defaultdict(list)\n        for employee, manager in enumerate(manager):\n            manager2employee[manager].append(employee)\n        @lru_cache(None)\n        def dfs(manager):\n            if not manager2employee[manager]:\n                return 0\n            return max([informTime[manager] + dfs(e) for e in manager2employee[manager]])\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        graph= defaultdict(list)\n        for child, parent in enumerate(manager):\n            \n            graph[parent].append(child)\n        q= deque([(headID, informTime[headID])])\n        maxval=0\n        while q:\n            head, time= q.popleft()\n            maxval= max(maxval,time)\n            for child in graph[head]:\n                q.append((child, time+ informTime[child]))\n        return maxval\n        \n        \n    \n            \n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(list(map(dfs, list(range(len(manager))))))\n        \n            \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        max_time = 0\n        node_stack = []\n        for node in manager:\n            time = 0\n            while node != -1:\n                node_stack.append(node)\n                node = manager[node]\n            while node_stack:\n                node = node_stack.pop()\n                time += informTime[node]\n                informTime[node] = time\n                manager[node] = -1\n                if time > max_time:\n                    max_time = time\n        return max_time", "class Solution:\n    class Node:\n        def __init__(self, id):\n            self.id = id\n            self.next = []\n            \n            \n    # BFS on a generated tree => O(n)\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if len(manager) == 0: return 0\n\n        directs = defaultdict(list)\n        for i, m in enumerate(manager):\n            directs[manager[i]].append(i)\n        # print(directs)\n        q = [(headID, 0)]\n        t = 0\n        while len(q) > 0:\n            (curr, currT) = q.pop(0)\n            t = max(t, currT)\n            if curr in directs:\n                for d in directs[curr]:\n                    q.append((d, currT + informTime[curr]))\n        return t\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        # create graph\n        # depth first search on the tree\n        # sum the maximum time it takes to inform each level\n        \n        relationships = {}\n        \n        for i in range(len(manager)):\n            if not manager[i] in relationships:\n                relationships[manager[i]] = [[],0]\n            relationships[manager[i]][0].append(i)\n            \n            if not i in relationships:\n                relationships[i] = [[],0]\n            relationships[i][1] = informTime[i]\n        \n        \n        def dfs(node, graph):\n            if not graph[node][0]: # leaf\n                return 0\n            else:\n                maxTime = 0\n                informTime = graph[node][1]\n                \n                for nbr in graph[node][0]:\n                    maxTime = max(maxTime, dfs(nbr, graph) + informTime)\n                \n                return maxTime\n        \n        return dfs(headID, relationships)\n                    \n            \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)\n\n            \n            \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # adjacency list\n        \n        adj = [[] for _ in range(n)]\n        s = headID\n        ans = 0\n        visited = [False] * n\n        \n        for i in range(n):\n            if manager[i] == -1:\n                continue\n            adj[manager[i]].append(i)\n            \n        def dfs(s, time):\n            nonlocal ans\n            Leaf = True\n            \n            for i in adj[s]:\n                if not visited[i]:\n                    Leaf = False\n                    visited[i] = True\n                    dfs(i, time + informTime[i])\n                    \n            if Leaf:\n                ans = max(ans, time)\n            \n            \n        dfs(s, informTime[s])\n        \n        return ans\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = {}\n        for i,man in enumerate(manager):\n            if man == -1:\n                continue\n            if man not in subs:\n                subs[man] = set()# if man != -1 else None\n            subs[man].add(i)\n            \n        #print(subs)\n        queue = [(headID, 0, 0)]\n        informTimes = {}\n        \n        while queue:\n            curr, level, informedAt = queue.pop()\n            if curr not in subs:\n                continue\n            emps = subs[curr]\n                            \n            for e in emps:\n                if level not in informTimes:\n                    informTimes[level] = []\n                currInformTime = informTime[curr] + informedAt\n                informTimes[level].append(currInformTime)\n                queue.append((e, level+1, currInformTime))\n        if not informTimes:\n            return 0\n        \n        maxInformTime = -1\n        for level, informTimesLevel in list(informTimes.items()):\n            maxInformTime = max(maxInformTime, max(informTimesLevel))\n        #maxLevel = max(informTimes.keys())\n        return maxInformTime\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 1:\n            return informTime[0]\n        graph = defaultdict(list)\n        \n        for i, m in enumerate(manager):\n            if m == -1:\n                continue\n            graph[m].append(i)\n        \n        #print( graph )\n        totalTime = []\n        def dfs( node, time=0):\n            nonlocal totalTime\n            if not graph[node]:\n                totalTime.append(time)\n            for e in graph[node]:\n                dfs(e, time+informTime[e])\n            \n        \n        dfs(headID, time=informTime[headID])\n        #print(totalTime)\n        return max(totalTime)", "class Employee:\n    def __init__(self, idx, inf_time):\n        self.idx = idx\n        self.inf_time = inf_time\n        self.subs = []\n\nclass Solution:            \n    def numOfMinutesCoool(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(map(dfs, manager))\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs_dct = defaultdict(list)\n        for empl, manager in enumerate(manager):\n            subs_dct[manager].append(empl)\n        \n        root = Employee(headID, informTime[headID])\n        def makeTree(node):\n            for sub in subs_dct[node.idx]:\n                node.subs.append(Employee(\n                    sub,\n                    node.inf_time + informTime[sub]\n                ))\n            for sub_node in node.subs:\n                makeTree(sub_node)\n        makeTree(root)\n        \n        total = 0\n        def dfs(node):\n            if not node.subs:\n                return node.inf_time\n            return max([dfs(sub_node) for sub_node in node.subs])\n        \n        return dfs(root)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 0:\n            return 0\n        \n        maxx = 0\n        cache = {}\n        for i in range(n):\n            curr = i\n            count = 0\n            while curr != headID:\n                curr = manager[curr]\n                count += informTime[curr]\n                if curr in cache:\n                    count += cache[curr]\n                    break\n            \n            # print(i, count)\n            cache[i] = count\n            # print(cache)\n            maxx = max(maxx, count)\n        return maxx", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(list)\n        for subord, manager in enumerate(managers):\n            graph[manager].append(subord)\n        \n        return self.dfs(headID, graph, informTime)\n    \n    def dfs(self, node, graph, informTime):\n        longest = 0\n        for child in graph[node]:\n            longest = max(longest, self.dfs(child, graph, informTime))\n        return longest + informTime[node]\n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n                      \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n                      \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n                      \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n            \n    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:\n        # 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\n        # -> not efficient, if I do that I explicitly build up a graph or adjacency matrix (manager -> employees)\n        # -> O(n) time + O(n) space\n        \n        # 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)\n        manager_to_employees = [[] for _ in managers]\n        for employee, manager in enumerate(managers):\n            if manager == -1: continue\n            manager_to_employees[manager].append(employee)\n        max_time = [0]\n        self.dfs(headID, informTime, manager_to_employees, 0, max_time)\n        return max_time[0]\n        \n    def dfs(self, ID, informTime, manager_to_employees, curr_time, max_time):\n        if not manager_to_employees[ID]: \n            max_time[0] = max(max_time[0], curr_time)\n        for employee in manager_to_employees[ID]:\n            self.dfs(employee, informTime, manager_to_employees, curr_time + informTime[ID], max_time)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n\n        reports = collections.defaultdict(set)\n        \n        for i, m in enumerate(manager):\n            if m == -1:\n                managerId = i\n            else:\n                reports[m].add(i)\n            \n        queue = collections.deque([(managerId, 0)])\n        maxT = 0\n        visited = set()\n        while queue:\n            person, time = queue.popleft()\n            if person in visited:\n                continue\n                \n            maxT = max(time, maxT)\n            \n            for r in reports[person]:\n                queue.append((r, time + informTime[person]))\n                \n    \n        return maxT\n            \n", "class Employee:\n    def __init__(self, employeeID, informTime):\n        self.id = employeeID\n        self.informTime = informTime \n        self.sub = []\n    \nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 1:\n            return informTime[0]\n        \n        head = self.buildEmpTree(n, manager, headID, informTime)\n        \n        return self.maxTime(head)\n        \n    def buildEmpTree(self, n, manager, headID, informTime):\n        s = {}\n        for i in range(n):\n            s[i] = Employee(i, informTime[i])\n            \n        for i in range(n):\n            if manager[i] == -1:\n                continue\n            s[manager[i]].sub.append(s[i])\n                    \n        return s[headID]\n        \n    def maxTime(self, root):\n        if not root.sub:\n            return root.informTime\n        \n        curMax = root.informTime\n        \n        for subordinate in root.sub:\n            curMax = max(curMax, root.informTime + self.maxTime(subordinate))\n        \n        return curMax\n", "class Solution:\n    def get_managers_delay(self, index: int, cache: List[int], manager: List[int], informTime: List[int]) -> int:        \n        if manager[index] == -1:\n            return informTime[index]\n        \n        if cache[index] != -1:\n            return cache[index]\n        \n        managers_delay = self.get_managers_delay(manager[index], cache, manager, informTime)\n        cache[index] = managers_delay + informTime[index]\n        \n        return cache[index]\n    \n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        cache = [-1] * n\n        max_inform_time = 0\n        \n        for i in range(n):\n            inform_time = self.get_managers_delay(i, cache, manager, informTime)\n            max_inform_time = max(max_inform_time, inform_time)\n            \n        return max_inform_time", "class Employee:\n    def __init__(self, idx, inf_time):\n        self.idx = idx\n        self.inf_time = inf_time\n        self.subs = []\n\nclass Solution:            \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs_dct = defaultdict(list)\n        for empl, manager in enumerate(manager):\n            subs_dct[manager].append(empl)\n        \n        root = Employee(headID, informTime[headID])\n        def makeTree(node):\n            for sub in subs_dct[node.idx]:\n                node.subs.append(Employee(\n                    sub,\n                    node.inf_time + informTime[sub]\n                ))\n            for sub_node in node.subs:\n                makeTree(sub_node)\n        makeTree(root)\n        \n        total = 0\n        def dfs(node):\n            if not node.subs:\n                return node.inf_time\n            return max([dfs(sub_node) for sub_node in node.subs])\n        \n        return dfs(root)", "from collections import defaultdict, deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if not n:\n            return 0\n        edges = defaultdict(list)\n        root = 0\n        for idx, val in enumerate(manager):\n            if val == -1:\n                root = idx\n            else:\n                edges[val].append(idx)\n        self.ans = 0\n        self.dfs(root, edges, informTime[root], informTime)\n        return self.ans\n    \n    def dfs(self, node, edges, curr_time, informTime):\n        self.ans = max(self.ans, curr_time)\n        for reporter in edges[node]:\n            self.dfs(reporter, edges, curr_time+informTime[reporter], informTime)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordinate = collections.defaultdict(list)\n        for i in range(n):\n            subordinate[manager[i]].append(i)\n        def solve(ID):\n            if subordinate[ID]:\n                return max(solve(i) for i in subordinate[ID]) + informTime[ID]\n            else:\n                return 0\n        return solve(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = defaultdict(list)\n        for index, managerId in enumerate(manager):\n            graph[managerId].append(index)\n        result = 0\n        def dfs(node, currentTime):\n            nonlocal graph, result\n            if node not in graph:\n                result = max(result, currentTime)\n                return\n            for emp in graph[node]:\n                dfs(emp, currentTime + informTime[node])\n        dfs(headID, 0)\n        return result", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # the employees are on a tree\n        # each time we go down one level, we wait X minutes\n        # the answer is the max among all leaf nodes (employees that don't manage)\n        \n        # first: creats aux data structures to support a tree-like interaction\n        # given an employee: know it's children\n        # build a map: key: employeeID -> List of children IDs\n        \n        # traverse the tree in BFS manner\n        # once a leaf is found, update the solution\n        \n        tree = {}\n        for i in range(len(manager)):\n            if manager[i] in tree:\n                tree[manager[i]].append(i)\n            else:\n                tree[manager[i]] = [i]\n        \n      \n        queue = [(headID, informTime[headID])]\n        solution = -1\n        while queue:\n            node, time = queue.pop(0)    \n            solution = max(solution, time)\n            \n            if node in tree:\n                for n in tree[node]:\n                    queue.append((n, time + informTime[n]))\n            \n        \n        return solution", "from collections import deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        adjList = {} \n        adjList[headID] = [] \n        for index, emp in enumerate(manager):\n            if emp == -1:\n                continue \n            if emp not in adjList: \n                adjList[emp] = []\n            adjList[emp].append(index)\n        \n        queue = deque()        \n        queue.append((headID, 0))\n\n        maxMinutes = float('-inf')\n        while queue:\n            for i in range(len(queue)):\n                idx, time = queue.popleft() \n                if informTime[idx] == 0:\n                    maxMinutes = max(maxMinutes, time)\n                else: \n                    for sub in adjList[idx]:\n                        queue.append((sub, time+informTime[idx]))\n                        \n        return maxMinutes ", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n == 0:\n            return 0\n        if n == 1:\n            return informTime[0]\n        dic = collections.defaultdict(list)\n        for i, x in enumerate(manager):\n            if x != -1:\n                dic[x].append(i)\n        def dfs(node):\n            time = 0\n            if not dic[node]:\n                return 0\n            for sub in dic[node]:\n                time = max(time, informTime[node] + dfs(sub))\n            return time\n        return dfs(headID)\n                \n                \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        graph = {i:[] for i in range(n)}\n        for child, parent in enumerate(manager):\n            if parent == -1: continue\n            graph[parent].append(child)\n        \n        time = 0\n        pq = [(0,headID)]\n        maxtime = 0\n        while pq:\n            curtime, curm = heapq.heappop(pq)\n            for nxt in graph[curm]:\n                heapq.heappush(pq, (curtime+informTime[curm], nxt))\n            maxtime = curtime\n        return maxtime\n            \n                    \n", "from collections import defaultdict\nclass Solution:\n    def __init__(self):\n        self.ans=0\n    \n    def helper(self, curr, children, timesofar):\n        if not children:\n            self.ans=max(self.ans, timesofar)\n        for i in children:\n            self.helper(i, self.graph[i], timesofar+self.informTime[i])\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        self.informTime=informTime\n        self.graph=defaultdict(list)\n        for idx,i in enumerate(manager):\n            self.graph[i].append(idx)\n        self.helper(headID, self.graph[headID], self.informTime[headID])\n        return self.ans", "class Solution:\n    class Node:\n        def __init__(self, id):\n            self.id = id\n            self.next = []\n            \n            \n    # BFS on a generated tree => O(n)\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if len(manager) == 0: return 0\n\n        directs = defaultdict(list)\n        for i, m in enumerate(manager):\n            directs[manager[i]].append(i)\n\n        q = deque([(headID, 0)])\n        t = 0\n        while len(q) > 0:\n            (curr, currT) = q.popleft()\n            t = max(t, currT)\n            if curr in directs:\n                for d in directs[curr]:\n                    q.append((d, currT + informTime[curr]))\n        return t\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        q = collections.deque([(headID, 0)])\n        subordinates = collections.defaultdict(list)\n        res = 0\n        for i, v in enumerate(manager):\n            subordinates[v].append(i)\n            \n        while q:\n            u, time = q.popleft()\n            res = max(res, time)\n            for v in subordinates[u]:\n                q.append((v, time + informTime[u]))\n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        total_time, company_dict = 0, {}\n        for i, m in enumerate(manager): # ix, emp\n            if m not in company_dict:\n                company_dict[m] = set([i]) # unique ix\n            else:\n                company_dict[m].add(i) # in dict {ix:ID ...}\n        \n        def get_emp_inf_time(manager, time):\n            nonlocal total_time\n            if manager not in company_dict: # new => {M:t ...}\n                total_time = max(total_time, time)\n                return\n            for e in company_dict[manager]: \n                time_to_inform = time + informTime[manager] # [1] mng : emp with time\n                get_emp_inf_time(e, time_to_inform) # rec. [2] emp time     \n        head = list(company_dict[-1])[0] # add the head\n        get_emp_inf_time(head, 0) # rec. [3]: add the last\n        return total_time", "import collections\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for i in range(len(manager)):\n            if manager[i] != -1:\n                graph[manager[i]].append(i)\n        queue = [(headID, 0)]\n        ans = 0\n        while queue:\n            temp = []\n            maxx = 0\n            for m, val in queue:\n                ans = max(ans, val)\n                for w in graph[m]:\n                    temp.append((w, val+informTime[m]))\n            queue = temp\n        return ans\n                        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        q = [(headID, 0)]\n        subordinates = collections.defaultdict(list)\n        res = 0\n        \n        for i, v in enumerate(manager):\n            subordinates[v].append(i)\n            \n        while q:\n            u, time = q.pop(0)\n            res = max(res, time)\n            for v in subordinates[u]:\n                q.append((v, time + informTime[u]))\n        return res\n    \n    # https://leetcode.com/problems/time-needed-to-inform-all-employees/discuss/532530/Python3-Easy-Python-Solution%3A-DijkstraBFSDFS\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n <= 1:\n            return 0\n        sub = collections.defaultdict(list)\n        for i in range(len(manager)):\n            sub[manager[i]].append(i)\n            \n        total = 0\n        q = collections.deque([(headID, 0)]) #id, time\n        while q:\n            employee, time = q.popleft()\n            if not sub[employee]:\n                total = max(total, time)\n            for nxt in sub[employee]:\n                q.append((nxt, time+informTime[employee]))\n        return total", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        from collections import defaultdict\n        \n        res = 0\n        children = defaultdict(list)\n        \n        for i, e in enumerate(manager):\n            children[e].append(i)\n        queue = collections.deque([(headID, informTime[headID])])\n        \n        while queue:\n            employeeID, time_needed = queue.popleft()\n            res = max(res, time_needed)\n            \n            for child in children[employeeID]:\n                queue.append((child, time_needed+informTime[child]))\n        \n        return res", "import collections\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        d = collections.defaultdict(list)\n        for i,k in enumerate(manager):\n            if i == headID:\n                continue\n            \n            d[k].append(i)\n        \n        q = [(0,headID)]\n        total = 0\n        while q :\n            time,node = q.pop(0)\n            for i in d[node]:\n                q.append((time+informTime[node],i))\n                total = max(total,time+informTime[node])\n        return total", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        queue = collections.deque([(headID, 0)])\n        subordinates = collections.defaultdict(list)\n        \n        for subordinate,supervisor in enumerate(manager):\n            subordinates[supervisor].append(subordinate)\n\n        time = 0\n        \n        while queue:\n            supervisor,currentInformTime = queue.popleft()\n            time = max(time,currentInformTime) # We are grabbing the maximum time over here \n            # 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 \n            \n            for subordinate in subordinates[supervisor]:\n                queue.append((subordinate,currentInformTime+informTime[supervisor]))\n        \n        return time   \n    \n# An alternate to line 13 would be to do xs.append(currentTime) and then on line 19 return max(xs)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        G = collections.defaultdict(list)\n        for i,v in enumerate(manager):\n            G[v].append(i)\n        \n        ans = 0\n        \n        qu = [(G[-1][0], 0)]\n        while qu:\n            n, v = qu.pop()\n            ans = max(ans,v)\n            for e in G[n]:\n                qu.append((e, v+informTime[n]))\n        return ans", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        cache = [-1] * n\n        def dfs(cur):\n            if cur == -1: return 0\n            if cache[cur] == -1:\n                cache[cur] = dfs(manager[cur]) + informTime[cur]\n            return cache[cur]\n        return max([dfs(i) for i in range(n)])\n\n    def numOfMinutes_5pct(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n            res = 0\n            for ii in range(len(manager)):\n                if informTime[ii]==0:\n                    temp = 0\n                    index = ii\n                    while index!=-1:\n                        temp += informTime[index]\n                        index = manager[index]\n                    res = max(res, temp)\n            return res\n\n            \n    def numOfMinutes_dfs_wrong(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        time = 0\n        ht = {}\n        for ii in range(len(manager)):\n            #if informTime[ii]==0: ## no sub\n            #    continue\n            if manager[ii]==-1: ##head\n                time = informTime[ii]\n                continue\n            if manager[ii] not in ht:\n                ht[manager[ii]] = {}\n                ht[manager[ii]]['subord'] = []\n                ht[manager[ii]]['time'] = informTime[ii]\n            ht[manager[ii]]['subord'].append(ii)\n        print(ht)\n            \n        queue = collections.deque() ##store managers only\n        queue.append(headID)\n        #print(queue)\n        informed = 1\n        while len(queue):\n            n_sub = len(queue)\n            #print('#########')\n            #print(n_sub)\n            for ii in range(n_sub):\n                m = queue.popleft()\n                #print('---------')\n                #print(m)\n                \n                #print(ht[m])\n                #if ii == 0:\n                #    time += ht[m]['time'] ##same time/parallel\n                if m in ht:\n                    for e in ht[m]['subord']:\n                        if e in ht: ##also a manager\n                            queue.append(e)\n                #print('after updating queue')\n                #print(queue)\n                #informed += 1\n        return time\n                \n                \n", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, managers: List[int], informTime: List[int]) -> int:\n        managerEmployeeTree = defaultdict(list)\n        for i, manager in enumerate(managers):\n            managerEmployeeTree[manager].append(i)\n        return self._traversal(managerEmployeeTree, headID, informTime)\n            \n    def _traversal(self, managerEmployeeTree, manager, informTime):\n        if managerEmployeeTree.get(manager):\n            maxInformTime = 0\n            for employee in managerEmployeeTree[manager]:\n                employeeInformTime = self._traversal(managerEmployeeTree, employee, informTime)\n                maxInformTime = max(maxInformTime, employeeInformTime)\n            return informTime[manager] + maxInformTime\n        return 0", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        dic = defaultdict(list)\n        for em,ma in enumerate(manager):\n            dic[ma].append(em)\n        \n        queue = deque([(headID,0)])\n        res = 0\n        while queue:\n            for _ in range(len(queue)):\n                ma,needed_time = queue.popleft()\n                res = max(res, needed_time)\n                for sub in dic[ma]:\n                    queue.append((sub,needed_time+informTime[ma]))\n        return res\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        q = collections.deque([(headID, 0)])\n        subordinates = collections.defaultdict(list)\n        res = 0\n        for i, v in enumerate(manager):\n            subordinates[v].append(i)\n            \n        while q:\n            u, time = q.popleft()\n            res = max(res, time)\n            for v in subordinates[u]:\n                q.append((v, time + informTime[u]))\n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        times = n * [-1]\n\n        def dfs(v):\n            times[v] = informTime[v]\n            \n            if manager[v] == -1:\n                return times[v]\n            \n            parent = manager[v]\n            \n            if times[parent] != -1:\n                times[v] += times[parent]\n                return times[v]\n            else:\n                times[v] += dfs(parent)\n                return times[v]\n        \n        for i, _emp in enumerate(manager):\n            if times[i] == -1:\n                dfs(i)\n        \n        return max(times)\n            \n        \n            \n            \n", "from typing import List\nfrom collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def build_graph():\n            g = defaultdict(list)\n            for employee_id in range(n):\n                manager_id = manager[employee_id]\n                if manager_id == -1:\n                    continue\n                g[manager_id].append(employee_id)\n            return g\n\n        g = build_graph()\n        max_time = [0]\n        def dfs(total_time, employee_id):\n            if employee_id not in g:\n                max_time[0] = max(total_time, max_time[0])\n                return\n            subordinates = g[employee_id]\n            for subordinate in subordinates:\n                dfs(total_time + informTime[employee_id], subordinate)\n        \n        dfs(0, headID)\n        return max_time[0]", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        # graph[a] = [# a list of A's subordinates]\n        # calculate time to reach any single employee at the leaf position \n        graph = collections.defaultdict(list)\n        for i, manager in enumerate(manager):\n            graph[manager].append(i)\n            \n        \n        # return the max time needed to inform all subs\n        def calculateTime(manager):\n            \n            if manager not in graph:\n                return 0 \n            \n            time = 0 \n            for emp in graph[manager]:\n                time = max(calculateTime(emp) , time)\n                \n            return time + informTime[manager]\n        \n        return calculateTime(headID)\n       \n         \n", "from collections import defaultdict\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # DFS Stack\n        self.max = 0\n        directSub = self.makeDirectSub(n,manager)\n        self.dfs(headID,directSub,informTime)\n        return self.max\n        \n    # def makeDirectSub(self, n, manager):\n    #     d = {employee: [] for employee in range(n)}\n    #     for employee in range(len(manager)):\n    #         if manager[employee] != -1:\n    #             d[manager[employee]].append(employee)\n    #     return d\n            \n    def makeDirectSub(self, n, manager):\n        d = defaultdict(list)\n        for sub, employee in enumerate(manager):\n            d[employee].append(sub)\n        return d\n        \n    def dfs(self, headID, directSub,informTime):\n        stk = [(headID,0)]\n        while stk:\n            employee, time = stk.pop()\n            self.max = max(self.max,time)\n            # add all subemployees and record the time it took them to get the information\n            for subEmp in directSub[employee]:\n                stk.append((subEmp,time+informTime[employee]))\n        return\n        \n    \n# from collections import deque, defaultdict\n\n# class Solution(object):\n#     def numOfMinutes(self, n, headID, manager, informTime):\n#         \\\"\\\"\\\"\n#         :type n: int\n#         :type headID: int\n#         :type manager: List[int]\n#         :type informTime: List[int]\n#         :rtype: int\n#         \\\"\\\"\\\"\n#         if n <= 1:\n#             return 0\n#         rst = 0\n#         childs = defaultdict(list)\n#         for idx, parent in enumerate(manager):\n#             childs[parent].append(idx)\n\n#         q = deque([(headID, informTime[headID])])\n#         while q:\n#             cur_id, cur_time = q.popleft()\n#             # calculate max\n#             rst = max(rst, cur_time)\n#             for child in childs[cur_id]:\n#                 q.append((child, cur_time + informTime[child]))\n#         return rst\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        from collections import defaultdict\n        \n        res = 0\n        \n        children = defaultdict(list)\n        \n        for i, e in enumerate(manager):\n            children[e].append(i)\n            \n        stack = [(headID, informTime[headID])]\n        \n        while stack:\n            employeeID, time_needed = stack.pop()\n            res = max(res, time_needed)\n            \n            for child in children[employeeID]:\n                stack.append((child, time_needed+informTime[child]))\n        \n        return res", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n <= 1:\n            return 0\n        d = defaultdict(list)\n        \n        for i in range(len(manager)):\n            d[manager[i]].append(i)\n        \n        self.ans = 0\n        \n        self.dfs(headID, d, 0, informTime)\n        return self.ans\n    \n    def dfs(self, node, d, totalTime, informTime):\n        self.ans = max(self.ans, totalTime)\n        \n        for sub in d[node]:\n            self.dfs(sub, d, totalTime + informTime[node], informTime)\n            \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        res = 0\n        graph = defaultdict(list)\n        for index, parent in enumerate(manager):\n            graph[parent].append(index)\n        \n        queue = deque([(headID, informTime[headID])])\n        while queue:\n            curId, curTime = queue.popleft()\n            res = max(res, curTime)\n            for child in graph[curId]:\n                queue.append((child, curTime + informTime[child]))\n        return res\n        \n        \n        \n        \n        \n        \n        \n#         rst = 0\n#         childs = defaultdict(list)\n#         for idx, parent in enumerate(manager):\n#             childs[parent].append(idx)\n\n#         q = deque([(headID, informTime[headID])])\n#         while q:\n#             cur_id, cur_time = q.popleft()\n#             # calculate max\n#             rst = max(rst, cur_time)\n#             for child in childs[cur_id]:\n#                 q.append((child, cur_time + informTime[child]))\n#         return rst\n", "class Solution:\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        from collections import defaultdict\n        graph = defaultdict(list)\n        for i, m in enumerate(manager): \n            graph[m].append(i)\n                \n        to_inform = deque([(headID, informTime[headID])])\n        max_t = 0\n        while to_inform:\n            m, t = to_inform.pop()\n            max_t = max(max_t, t)\n            for s in graph[m]:\n                to_inform.append((s, t + informTime[s]))\n            \n        return max_t", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        timeNeed = [-1] * n\n        \n        def get_info_time(m):\n            if(timeNeed[m] != -1):\n                return timeNeed[m]\n            m_dad = manager[m]\n            if(m_dad == -1):\n                timeNeed[m] = 0\n            else:\n                timeNeed[m] = get_info_time(m_dad) + informTime[m_dad]\n            return timeNeed[m]\n        \n\n        for i in range(n):\n            get_info_time(i)\n        \n        return max(timeNeed)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = collections.defaultdict(list)\n        for i in range(len(manager)):\n            if manager[i] == -1:\n                continue\n            graph[manager[i]].append(i)\n        return self.dfs(headID, graph, informTime)\n    \n    def dfs(self, head, graph, informTime):\n        time = 0\n        for employee in graph[head]:\n            time = max(time, self.dfs(employee, graph, informTime))\n        return informTime[head] + time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        report = collections.defaultdict(list)\n        for idx, i in enumerate(manager):\n            report[i].append(idx)\n        \n        queue = [(headID, informTime[headID])]\n        maxT = 0\n        while queue:\n            n, t  = queue.pop(0)\n            maxT = max(maxT, t)\n            for r in report[n]:\n                queue.append((r, t+informTime[r]))\n        \n        return maxT", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        managerMapping = {}\n        maxTime = 0\n        def dfs(currentTime, currentEmployee, manangerMapping):\n            nonlocal maxTime\n            if currentEmployee not in managerMapping:\n                maxTime = max(currentTime, maxTime)\n            else:\n                directs = managerMapping[currentEmployee]\n                for direct in directs:\n                    dfs(currentTime + informTime[currentEmployee], direct, managerMapping)\n                    \n        for i in range(len(manager)):\n            if manager[i] in managerMapping:\n                managerMapping[manager[i]].append(i)\n            else:\n                managerMapping[manager[i]] = [i]\n        dfs(0, headID, managerMapping)\n        return maxTime", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if n <= 1:\n            return 0\n        rst = 0\n        childs = defaultdict(list)\n        for idx, parent in enumerate(manager):\n            childs[parent].append(idx)\n\n        queue = deque([(headID, informTime[headID])])\n        while queue:\n            cur_id, cur_time = queue.popleft()\n            # calculate max\n            rst = max(rst, cur_time)\n            for child in childs[cur_id]:\n                queue.append((child, cur_time + informTime[child]))\n        return rst", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        d = collections.defaultdict(list)\n        for i in range(n):\n            d[ manager[i] ].append(i)\n        \n        res = 0\n        que = collections.deque( [ [ d[-1][0], 0 ] ] )\n        \n        while que:\n            cur, time = que.popleft()\n            res = max(res, time)\n            time += informTime[cur]\n            \n            for t in d[cur]:\n                que.append( [t, time] )\n        \n        return res\n        \n", "from collections import deque\nclass Solution:\n    \n    def max_at_level(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = deque([headID])\n        final_time_list = []\n        while len(subs) > 0:\n            managers_at_level = len(subs)\n            level_time_list = []\n            for i in range(managers_at_level):\n                current_sub = subs.popleft()\n                level_time_list.append(informTime[current_sub])\n                subs += [index for index, val in enumerate(manager) if val == current_sub ]\n            final_time_list.append(level_time_list)\n        \n        total_time = 0\n        for level_list in final_time_list:\n            total_time += max(level_list) \n        return total_time\n    \n    def numOfMinutesRecu(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subs = [index for index, val in enumerate(manager) if val == headID]\n        if subs:\n            time_sum = []\n            for sub in subs:\n                time_sum.append(self.numOfMinutes(n, sub, manager, informTime) + informTime[headID])\n            return max(time_sum)\n        else:\n            return informTime[headID]\n        \n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        stack = [(headID, informTime[headID])]\n        res = 0\n        \n        children = defaultdict(list)\n        for i, e in enumerate(manager):\n            children[e].append(i)\n        \n        while stack:\n            curr_id, curr_time = stack.pop()\n            res = max(res, curr_time)\n            #children = [index for index, val in enumerate(manager) if val == curr_id]\n            for child in children[curr_id]:\n                stack.append((child, curr_time+informTime[child]))\n        return res", "from collections import defaultdict \nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        if len(manager) <= 1:\n            return informTime[headID]\n        \n        graph = defaultdict(list)\n            \n        q = deque()\n        \n        def bfs(graph):\n            time_so_far = 0\n            while q:\n                node, time_taken = q.popleft()\n                time_so_far  = max(time_so_far, time_taken)\n                for next_node in graph[node]:\n                    q.append([next_node, time_taken + informTime[next_node]])\n            return time_so_far        \n        \n        for m in range(len(manager)):\n            if manager[m] != -1:\n                graph[manager[m]].append(m)\n                  \n        q.append([headID, informTime[headID]])\n        \n        return  bfs(graph)\n        \n        \n         \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n\n        sub = collections.defaultdict(list)\n        for i,v in enumerate(manager):\n            sub[v].append(i)\n        res = -float('inf')\n        def dfs(fa,time):\n            nonlocal res\n            if not sub[fa]: \n                res = max(res,time)\n            else:\n                for son in sub[fa]:\n                    dfs(son,time+informTime[fa])\n            return\n        dfs(headID,0)\n        return res if res < float('inf') else -1\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        if len(manager) == 1:\n            return informTime[0]\n        \n        d=defaultdict(list)\n        for i,e in enumerate(manager):\n            d[e].append(i)\n        #print(d)\n        \n        '''\n        q=[d[-1]]\n        mt=1\n        time=-1\n        while q:\n            time+=mt\n            mt=0\n            print(\\\"TIme:- \\\",time,\\\"  \\\",\\\"Queue:- \\\",q)\n            n=len(q)\n            for i in range(n):\n                x=q.pop(0)\n                if type(x) != int:\n                    mt = max(mt,informTime[x[0]])\n                    for e in d[x[0]]:\n                        q.append(e)\n                else:\n                    mt = max(mt,informTime[x])\n                    for e in d[x]:\n                        q.append(e)\n        return time\n        '''\n        \n        self.time = 0\n        def dfs(x,mt):\n                \n            if type(x)!=int:\n                if not d[x[0]]:\n                    self.time = max(mt,self.time)\n                for e in d[x[0]]:\n                    dfs(e,mt+informTime[x[0]])\n            else:\n                if not d[x]:\n                    self.time = max(mt,self.time)\n                for e in d[x]:\n                    dfs(e,mt+informTime[x])\n                    \n        dfs(d[-1],0)\n        return self.time\n        \n                \n            \n            \n            \n            \n            \n                \n", "'''\nn = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]\n\n'''\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(node):\n            if not graph[node]:\n                return 0\n            else:\n                max_time = 0\n                for child in graph[node]:\n                    max_time = max(max_time,dfs(child))\n                return informTime[node]+max_time\n            \n        graph = collections.defaultdict(list)\n        for i,j in enumerate(manager):\n            graph[j].append(i)\n            \n        return dfs(headID)\n        \n", "class Solution:\n    def numOfMinutes(self, n, headID, manager, informTime):\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(map(dfs, range(n)))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        sub = defaultdict(list)\n        for i, m in enumerate(manager):\n            sub[m].append(i)\n            \n        def dfs(i):\n            m = 0\n            for j in sub[i]:\n                m = max(m, dfs(j))\n            return m + informTime[i]\n    \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        hmap = {}\n        for i, m in enumerate(manager):\n            hmap[m] = hmap.get(m, []) + [i]\n        \n        stack = [(headID, 0)]\n        res = 0\n        \n        while stack:\n            m, val = stack.pop()\n            res = max(res, val)\n            if m not in hmap:\n                continue\n            val += informTime[m]\n            for e in hmap[m]:\n                stack.append((e, val))\n        \n        return res", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # Convert to a tree structure\n        \n        graph = collections.defaultdict(list)\n        for person, boss in enumerate(manager):\n            if boss != -1:\n                graph[boss].append(person)\n            \n        # Then do a bfs\n        # Person with max_time is the answer\n        # Guaranteed to be a tree, no need for seen\n        queue = [(headID, 0)]\n        max_time = - float('inf')\n        \n        while queue:\n            nq = []\n            \n            for boss, time in queue:\n                max_time = max(max_time, time)\n                \n                for employee in graph[boss]:\n                    nq.append((employee, time + informTime[boss]))\n            queue = nq\n            \n        return max_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph = {}\n        res = 0\n        for e, m in enumerate(manager):\n            graph[m] = graph.get(m, []) + [e]\n        stack = [(headID, 0)]\n        while stack:\n            curr, time = stack.pop()\n            res = max(res, time)\n            if curr in graph:\n                for e in graph[curr]:\n                    stack.append((e, time + informTime[curr]))\n        return res", "class Solution:\n    def dfs(self,node,visited,graph,minute,informTime):\n        visited[node]=minute\n        for neighbour in graph[node]:\n            self.dfs(neighbour,visited,graph,minute+informTime[node],informTime)\n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        graph={}\n        for i in range(n):\n            graph[i]=[]\n        for i in range(len(manager)):\n            if manager[i]!=-1:\n                graph[manager[i]]+=[i]\n        visited=[-1 for i in range(n)]\n        visited[headID]=0\n        self.dfs(headID,visited,graph,0,informTime)\n        return max(visited)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        d = collections.defaultdict(list)\n        \n        for i in range(n):\n            d[ manager[i] ].append(i)\n        \n                \n        def dfs(i):\n            if not d[i]:\n                return 0\n            \n            return informTime[i]+max( [ dfs(t) for t in d[i]  ] )\n        \n        return dfs( d[-1][0] )\n    \n        \n        \n        \n        \n#         d = collections.defaultdict(list)\n#         for i in range(n):\n#             d[ manager[i] ].append(i)\n        \n#         res = 0\n#         que = collections.deque( [ [ d[-1][0], 0 ] ] )\n        \n#         while que:\n#             cur, time = que.popleft()\n#             res = max(res, time)\n#             time += informTime[cur]\n            \n#             for t in d[cur]:\n#                 que.append( [t, time] )\n        \n#         return res\n        \n", "class Solution:\n    def helper(self, node, sub, informTime):\n        if node not in sub or len(sub[node]) == 0:\n            return informTime[node]\n        times = [self.helper(x, sub, informTime) for x in sub[node]]\n        return max(times) + informTime[node]\n    \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        sub = defaultdict(list)\n        for i, m in enumerate(manager):\n            sub[m].append(i)\n        return self.helper(headID, sub, informTime)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def get_inform_time(mgr):\n            subords = g[mgr]\n            time_to_inform = 0\n            for sub in subords:\n                time_to_inform = max(time_to_inform, get_inform_time(sub))\n                \n            return time_to_inform + informTime[mgr]\n                \n        \n        g = collections.defaultdict(list)\n        for employee, mgr in enumerate(manager):\n            g[mgr].append(employee)\n            \n        return get_inform_time(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        subordination = collections.defaultdict(list)\n        for i, mID in enumerate(manager):\n            if mID != -1:\n                subordination[mID].append(i)\n        \n        def dfs(mID: int) -> int:\n            maxTime = 0\n            for sub in subordination[mID]:\n                maxTime = max(maxTime, informTime[mID] + dfs(sub))\n            return maxTime\n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(i):\n            if manager[i] != -1:\n                informTime[i] += dfs(manager[i])\n                manager[i] = -1\n            return informTime[i]\n        return max(map(dfs, range(n)))", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for _ in range(n)]\n        \n        for i, m in enumerate(manager):\n            if m >= 0:\n                children[m].append(i)\n        \n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n, headID, manager, informTime):\n        children = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: \n                children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)\n\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        for i, m in enumerate(manager):\n            if m >= 0: children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)\n        # subordinates = [[] for _ in range(n)]\n        # for i in range(n):\n        #     for j in range(n):\n        #         if manager[j] == i:\n        #             subordinates[i].append(j)\n        # res = [0] * n\n#         # print(subordinates)l\n#         def helper(id, current_time):\n#             time = informTime[id] + current_time\n#             subs = subordinates[id]\n#             if subs:\n#                 for k in subs: helper(k, time)\n#             else:\n#                 res[id] = time               \n        \n#         helper(headID, 0)\n#         return max(res)\n#         queue = deque([(manager.index(-1), 0)])\n#         while queue:\n#             i, t = queue.popleft()\n#             for j in subordinates[i]:\n#                 res[j] = t\n#                 queue.append((j, t + informTime[i]))\n#         return max(res)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        tree = collections.defaultdict(list)\n        time = {}\n        for i, (m, t) in enumerate(zip(manager, informTime)):\n            tree[m].append(i)\n            time[i] = t\n        \n        ans = 0\n        \n        def dfs(node, t):\n            nonlocal ans\n            \n            t += time[node]\n            for child in tree[node]:\n                dfs(child, t)\n            ans = max(ans, t)\n        \n        dfs(headID, 0)\n        return ans", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # DFS Stack\n        self.max = 0\n        directSub = self.makeDirectSub(manager)\n        self.dfs(headID,directSub,informTime)\n        return self.max\n        \n    def makeDirectSub(self, manager):\n        d = {new_list: [] for new_list in range(len(manager))}\n\n        for employee in range(len(manager)):\n            if manager[employee] != -1:\n                d[manager[employee]].append(employee)\n        return d\n            \n        \n    def dfs(self, headID, directSub,informTime):\n        stk = [(headID,0)]\n        while stk:\n            employee, time = stk.pop()\n            self.max = max(self.max,time)\n            # add all subemployees and record the time it took them to get the information\n            for subEmp in directSub[employee]:\n                stk.append((subEmp,time+informTime[employee]))\n        return\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for _ in range(n)]\n        for i, x in enumerate(manager):\n            if x>=0: children[x].append(i)\n            \n        def dfs(p):\n            return max([dfs(x) for x in children[p]] or [0]) + informTime[p]\n        \n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        children = [[] for i in range(n)]\n        # construct the tree\n        # children[m] is the list of direct subordinates\n        # of m\n        for i, m in enumerate(manager):\n            if m >= 0:\n                children[m].append(i)\n        \n        # the time for a maganer = max(his employee's time)\n        # + inforTime[manager]\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        \n        return dfs(headID)", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        # Top down approach is ok\n        # Bottom up approach: COPIED\n        # Idea is: Given any employee, recursively (going up the chain of command) compute its time to \n        # reach the head. Then, for a different employee, check if its managers computed value is set\n        # via the dfs call. If it is, use it directly, else make the dfs call as before, and so on for each employee.\n        \n        # Lee's solution uses manager as a way to mark if the dfs call for an employee has been made.\n        # Let's do it assuming we should not modify manager => maintain a separate array\n        # This is basically the usual DFS on the directed graph as provided\n        # With each DFS visit, we add the informTime of an employee's manager to the informTime of the employee\n        # So informTime will now tell you the time to reach the head from the employee\n        # To avoid using visited[], we'd need to modify manager\n        \n        # def dfs_visit(u):\n            # visited[u] = True\n            # v = manager[u]\n            # if v == -1:\n            #     return 0\n            # else:\n            #     if not visited[v]:\n            #         _ = dfs_visit(v)\n            #     informTime[u] += informTime[v]\n            #     return informTime[u]\n\n        # Without visited, modifying manager\n        def dfs_visit(u):\n            v = manager[u]\n            if manager[v] != -1:\n                dfs_visit(v)\n            informTime[u] += informTime[v]\n            manager[u] = -1\n            return informTime[u]\n            \n        #visited = [False]*n\n        res = 0\n        for u in range(n):\n            # if not visited[u]:\n            if manager[u] != -1:\n                res = max(res, dfs_visit(u))\n        return res\n                    \n", "class Solution:\n    over_all_max_time = 0\n    def DFS(self ,edgeList , max_time , headID , informTime):\n        if len(edgeList[headID]) == 0:\n            Solution.over_all_max_time = max(Solution.over_all_max_time , max_time)\n            return\n        \n        for emp in edgeList[headID]:\n            max_time += informTime[headID]\n            self.DFS(edgeList , max_time , emp , informTime)\n            max_time -= informTime[headID]\n        \n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        Solution.over_all_max_time = 0\n        edgeList = {i:[] for i in range(n)}\n        for cur_emp in range(n):\n            cur_emp_manager = manager[cur_emp]\n            if cur_emp_manager != -1:\n                edgeList[cur_emp_manager].append(cur_emp)\n        self.DFS(edgeList , 0 , headID , informTime)\n        return Solution.over_all_max_time\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        n = len(manager)\n        graph = collections.defaultdict(list)\n        \n        for i in range(n):\n            graph[manager[i]].append(i)\n            \n            \n        q = [(headID, 0)]\n        res = 0\n        \n        while q:\n            node, time = q.pop(0)\n            res = max(res, time)\n            for nei in graph[node]:\n                q.append((nei, time + informTime[node]))\n        \n        return res\n        \n        \n", "class Solution:\n\n    def numOfMinutes(self, n, headID, manager, informTime):\n        time_when_informed = {}\n        total = 0\n\n        time_when_informed[headID] = 0\n\n        def get_informed_time(node):\n            if node in time_when_informed:\n                return time_when_informed[node]\n            else:\n                ret = informTime[manager[node]] + get_informed_time(manager[node])\n                time_when_informed[node] = ret\n                return ret\n\n        ans = 0\n        for node in range(len(manager)):\n            if node not in time_when_informed:\n                ans = max(ans, get_informed_time(node))\n            else:\n                ans = max(ans, time_when_informed[node])\n\n        return ans", "from collections import deque\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        visited = set()\n        graph = defaultdict(list)\n        for idx, m in enumerate(manager):\n            graph[m].append(idx)\n\n        max_val = 0        \n        q = deque()\n        q.append([headID, 0])\n        \n        while len(q):\n            parent, weight = q.popleft()\n            max_val = max(max_val, weight)\n            for child in graph[parent]:\n                q.append((child, weight + informTime[parent]))\n        \n        return max_val", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        #DFS, find longest path from root to leaf\n        #TC: O(N)\n        #SC: O(N)\n        child = defaultdict(list)\n        boss = -1\n        res = 0\n        for i in range(len(manager)):\n            if manager[i] == -1:\n                boss = i\n                continue\n            child[manager[i]].append(i)\n        def dfs(i, time):\n            nonlocal res\n            #time taken for the information to reach i\n            # print(i, child[i])\n            res = max(res, time)\n            for j in range(len(child[i])):\n                dfs(child[i][j], time + informTime[i])\n        dfs(boss, 0)\n        return res\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def dfs(node, cost):\n            nonlocal ans\n            cost += informTime[node]\n            \n            ans = max(ans, cost)\n            \n            for nei in graph[node]:\n                if nei not in seen:\n                    seen.add(nei)\n                    dfs(nei, cost)\n        \n        graph = collections.defaultdict(list)\n        \n        for i, man in enumerate(manager):\n            if man == -1: continue\n            graph[man].append(i)\n        \n        seen = set()\n        \n        ans = 0\n        \n        dfs(headID, 0)\n        \n        return ans", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n      graph = collections.defaultdict(list)\n      for i in range(n):\n        graph[manager[i]].append(i)\n        \n        \n      def dfs(manager, curr_time):\n        self.max_time = max(self.max_time, curr_time)\n        for subordinate in graph[manager]:\n          dfs(subordinate, curr_time + informTime[manager])\n      \n      \n      self.max_time = 0\n      dfs(headID, 0)\n      return self.max_time", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        children = collections.defaultdict(list)\n        for i, m in enumerate(manager):\n            if m >= 0: children[m].append(i)\n\n        def dfs(i):\n            return max([dfs(j) for j in children[i]] or [0]) + informTime[i]\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        managerMap = defaultdict(list)\n\n        for i, v in enumerate(manager):\n            managerMap[v].append(i)\n\n        def dfs(mgr):\n            return max([dfs(emp) for emp in managerMap[mgr]] or [0]) + informTime[mgr]\n\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        def find_ttk(e):\n            if ttk[e]==-1:\n                m = manager[e]\n                if m == -1:\n                    ttk[e]=0\n                else:\n                    ttk[e]=find_ttk(m)+informTime[m]\n            return ttk[e]\n        \n        ttk = [-1]*n\n        for e in range(n):\n            if ttk[e]==-1:\n                ttk[e]=find_ttk(e)\n                \n        return max(ttk)", "from collections import defaultdict\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        sub = defaultdict(list)\n        for i, s in enumerate(manager):\n            sub[s] += [i]\n        \n        def dfs(cur):\n            return max([dfs(employee) for employee in sub[cur]] or [0]) + informTime[cur]\n        return dfs(headID)", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        minutes = 0\n\n        # construct adj list\n        g = defaultdict(list)\n        for i in range(n):\n            g[manager[i]].append(i)\n\n        # dfs \n        def dfs(eid, elapsed):\n            nonlocal minutes\n            if not g[eid]:\n                minutes = max(minutes, elapsed)\n            for sub in g[eid]:\n                dfs(sub, elapsed+informTime[eid])\n        dfs(headID, 0)\n        return minutes\n        \n", "from collections import deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        graph = {}\n        \n        for emp,manager in enumerate(manager):\n            if manager in graph:\n                graph[manager].append(emp)\n            else:\n                graph[manager] = [emp]\n                \n        ans = {}\n        \n        ans[headID] = 0\n        \n        Queue = deque()\n        Queue.append(headID)\n        maxele = 0\n        while Queue:\n            cid = Queue.popleft()\n            if cid not in graph:\n                continue\n            for emp in graph[cid]:\n                ans[emp] = ans[cid] + informTime[cid]\n                maxele = max(maxele, ans[emp])\n                Queue.append(emp)\n                \n        return maxele\n            \n        \n        \n        \n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        G = {i:[] for i in range(n)} # map node to a list of its children\n        for i in range(len(manager)):\n            if manager[i] > -1:\n                G[manager[i]].append(i)\n        self.ans = 0\n        def dfs(root=headID,timeUsed=0):\n            if not G[root]:\n                #self.ans = max(self.ans,timeUsed)\n                return timeUsed\n            # for child in G[root]:\n            #     dfs(child,timeUsed + informTime[root])\n            \n            return max([dfs(child,timeUsed + informTime[root]) for child in G[root]])\n        \n        return dfs()\n        \n        \n#         from collections import deque\n#         def bfs(root=headID):\n#             ans = 0\n#             Q = deque()\n#             Q.append([root])\n            \n#             while Q:\n#                 nodes = Q.popleft()\n#                 ans += max([informTime[node] for node in nodes])\n                \n#                 next_lvl = []\n#                 for node in nodes:\n#                     for child in G[node]:\n#                         next_lvl.append(child)\n#                 if next_lvl:\n#                     Q.append(next_lvl)\n#             return ans\n#         return bfs()\n", "import heapq\n\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        hierachy = {}\n        for idx, m in enumerate(manager):\n            if m not in hierachy: \n                hierachy[m] = []\n            hierachy[m].append(idx)\n            \n        time_needed = [-1] * n\n        time_needed[headID] = 0\n\n        # Dijkstra's algorithm. There's not really such a need. \n        # There's no need to keep track of 'visited' because each node will be visited once anyway. \n        q = [(0, headID)]\n        \n        while q:\n            cost, node = heapq.heappop(q)\n            time_needed[node] = cost\n            for nei in hierachy.get(node, []):\n                heapq.heappush(q, (time_needed[node] + informTime[node], nei))\n                \n        return max(time_needed)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        g = defaultdict(list)\n        for e,m in enumerate(manager):\n            it = informTime[m]\n            g[m].append((e,it))\n            \n        self.mc = 0\n        def dfs(node,cost):\n            self.mc = max(self.mc, cost)\n            \n            for child,cc in g[node]:\n                dfs(child,cost + cc)\n        \n        dfs(headID,0)\n                \n        return self.mc\n            \n            \n            \n", "from collections import defaultdict\nfrom collections import deque\nclass Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        \n        eg = defaultdict(set)\n        mgr = None\n        for i,man in enumerate(manager):\n            if man != -1:\n                eg[man].add(i)\n            else:\n                mgr = i\n        # print(eg)\n        time_map = {}\n        for i, time in enumerate(informTime):\n            time_map[i] = time\n#         we are looking for the max path length when a leaf node is reached\n        q = deque()\n        q.append((mgr, time_map[mgr]))\n        # print(time_map, q)\n        max_it = -float('inf')\n        \n        while q:\n            node, dist = q.popleft()\n            # print(dist)\n            if len(eg[node]) == 0:\n                max_it = max(max_it, dist)\n            \n            for neighbor in eg[node]:\n                q.append((neighbor, dist+time_map[neighbor]))\n        \n        return max_it\n        \n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        #           headID\n        #         /        \\\\\n        #      sub1         sub2\n        #      / \\\\          / \\\\\n        #   sub11 sub12  sub21 sub22\n        \n        subs = [[] for i in range(n)]\n        for i, m in enumerate (manager):\n            if m != -1:\n                subs[m].append(i)\n                \n        def my_dfs(m):\n            \n            if not len(subs[m]): return informTime[m]\n            return max([my_dfs(s) for s in subs[m]]) + informTime[m]\n        \n        return my_dfs(headID)\n", "class Solution:\n    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:\n        company_dict = {}\n        total_time = 0\n        \n        for i, m in enumerate(manager):\n            if m not in company_dict:\n                company_dict[m] = set([i])\n            else:\n                company_dict[m].add(i)\n        \n        def get_emp_inf_time(manager, time):\n            nonlocal total_time\n            if manager not in company_dict:\n                total_time = max(total_time, time)\n                return\n            for e in company_dict[manager]:\n                time_to_inform = time + informTime[manager]\n                get_emp_inf_time(e, time_to_inform)\n        \n        head = list(company_dict[-1])[0]\n        get_emp_inf_time(head, 0)\n        return total_time"]