1376 Time Needed to Inform All Employees

https://leetcode.com/problems/time-needed-to-inform-all-employees/submissions/

class Solution {
    private class Node {
        int time;
        List<Node> subs;
        public Node(int t) {
            time = t;
            subs = new ArrayList<>();
        }
    }
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        Node[] emps = new Node[n];
        emps[headID] = new Node(informTime[headID]);
        buildGraph(emps, manager, informTime);
        dfs(emps[headID]);
        return dfs(emps[headID]);
    }
    private int dfs(Node man) {
        if (man == null) return 0;
        int tmp = 0;
        for (Node sub : man.subs) {
            tmp = Math.max(tmp, dfs(sub));
        }
        return tmp + man.time;
    }
    private void buildGraph(Node[] emps, int[] manager, int[] informTime) {
        for (int i = 0; i < manager.length; i++) {
            if (manager[i] == -1) continue;
            Node emp = emps[i];
            if (emp == null) emp = new Node(informTime[i]);
            emps[i] = emp;
            
            Node man = emps[manager[i]];
            if (man == null) man = new Node(informTime[manager[i]]);
            emps[manager[i]] = man;
            man.subs.add(emp);
        }
    }
}

怎么会有这么无聊的题啊 不过还是要注意这里是取下属里通知花的最长的时间

注意这里看起来好像可以用bfs按层次取每次通知最长时间然后把每层加起来，但是这样并不正确，原因是有些人通知到下一层需要花超过其他人通知到下面两层的时间，别人都通知完了他还没通知完，最后的时间以他通知一层为准，而不需要再加上别人通知下一层的时间，单单一层一层的看并不能知道这一点，所以最好还是用dfs，每次取下属通知花的总共的最长时间加上自己通知到下属的时间。

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        // manager idx -> list of sub idx
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < manager.length; i++) {
            int man = manager[i];
            List<Integer> list = map.get(man);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(i);
            map.put(man, list);
        }
        return dfs(headID, map, informTime);
    } 
    private int dfs(int e, Map<Integer, List<Integer>> map, int[] informTime) {
        if (map.get(e) == null) {
            return 0;
        }
        List<Integer> list = map.get(e);
        int tmp = 0;
        for (int s : list) {
            tmp = Math.max(tmp, dfs(s, map, informTime));
        }
        return informTime[e] + tmp;
    }
}