Concise explanation with a Picture for Visualization
\nKey idea\nWhenever you are at a node, say p, you will collect all apples in p\u2019s subtree before returning back to the original root. This will avoid trave
\n**Key idea**\nWhenever you are at a node, say p, you will collect all apples in p\u2019s subtree before returning back to the original root. This will avoid traveling the same path multiple times. \nSay, root is where we start, p is a node in the tree and p has two children - child1, child2 - and both of them have an apple each.\n`root -> p -> child1 -> p -> child2 -> p -> root `is always going to be better than\n`root-> p -> child1 -> p -> root -> p -> child2 -> p -> root`.\n\nSo now it becomes a simple graph traversal problem, particularly DFS where we visit all children of the node first and then go back the other nodes.\n\n**Algorithm**\n1. Because you have the list of edges, construct the graph first to have a better representation of the graph.\n2. For each node, check if any of its children have apples and find the total cost in terms of time in seconds of collecting those.\n3. If there is at least one child with an apple, then we have to collect it. So we will also have to add the cost (time required) of reaching that node.\n4. return the total time.\n\nFollowing image should help in understanding better.\n\n**Please upvote** if you find this helpful, it would be encouraging! \n\nLet me know if something is unclear and I will fix it. :)\nThanks.\n\n\n![image](https://assets.leetcode.com/users/interviewrecipes/image_1591669743.png)\n\n\n\n\n**[EDIT]**\nIt looks like some cases were failing because I assumed I won\'t need the bidirectional graph. As correctly pointed out by @hiepit, I was wrong. Fixed the code. :)\n\n**C++**\n```\nclass Solution {\npublic:\n    unordered_map<int, vector<int>> g; // to store the graph\n    unordered_map<int, bool> visited; // to stop exploring same nodes again and again.\n\t\n    void createGraph(vector<vector<int>>& edges) {\n      for (auto e: edges) {\n        g[e[0]].push_back(e[1]); // adjecency list representation\n\t\tg[e[1]].push_back(e[0]); // adjecency list representation\n      }\n    }\n  \n    int dfs(int node, int myCost, vector<bool>& hasApple) {\n\t  if (visited[node]) {\n\t\t  return 0;\n\t  }\n\t  visited[node] = true;\n\t  \n      int childrenCost = 0; // cost of traversing all children. \n      for (auto x: g[node]) { \n        childrenCost += dfs(x, 2, hasApple);  // check recursively for all apples.\n      }\n\n      if (childrenCost == 0 && hasApple[node] == false) {\n\t  // If no child has apples, then we won\'t traverse the subtree, so cost will be zero.\n\t  // similarly, if current node also does not have the apple, we won\'t traverse this branch at all, so cost will be zero.\n        return 0;\n      }\n\t  \n\t  // Children has at least one apple or the current node has an apple, so add those costs.\n      return (childrenCost + myCost);\n    }\n  \n    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {\n      createGraph(edges); // construct the graph first.\n      return dfs(0, 0, hasApple); // cost of reaching the root is 0. For all others, its 2.\n    }\n};\n\n```\n\n**Java**\n```\nclass Solution {\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        \n        Map<Integer, List<Integer>> graph = createGraph(edges); // to store the graph\n        Map<Integer, Boolean> visited = new HashMap<>();\n\t\t\n        return dfs(graph, 0, hasApple, 0, visited); // cost of reaching the root is 0. For all others, its 2.\n      \n    }\n    \n    private int dfs(Map<Integer, List<Integer>> graph, int node, List<Boolean> hasApple, int myCost, Map<Integer, Boolean> visited) {\n        Boolean v = visited.getOrDefault(node, false);\n\t\tif (v) {\n\t\t\treturn 0;\n\t\t}\n\t\tvisited.put(node, true);\n\t\t\n        int childrenCost = 0; // cost of traversing all children. \n      \n        for(int n : graph.getOrDefault(node, new ArrayList<>())) {\n            childrenCost += dfs(graph, n, hasApple, 2, visited); // check recursively for all apples in subtrees.\n        }\n      \n        if (childrenCost == 0 && hasApple.get(node) == false) {\n          // If no child has apples, then we won\'t traverse the subtree, so cost will be zero.\n          // similarly, if current node also does not have the apple, we won\'t traverse this branch at all, so cost will be zero.\n          return 0;\n        }\n      \n        return childrenCost + myCost;\n    }\n    \n    private Map<Integer, List<Integer>> createGraph(int[][] edges) {\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n      \n        for(int i = 0; i < edges.length; i++) {\n            List<Integer> list = graph.getOrDefault(edges[i][0], new ArrayList<>()); // Adjecency list representation.\n            list.add(edges[i][1]);\n            graph.put(edges[i][0], list);\n\t\t\t\n\t\t\tlist = graph.getOrDefault(edges[i][1], new ArrayList<>()); // Adjecency list representation.\n            list.add(edges[i][0]);\n            graph.put(edges[i][1], list);\n        }\n      \n        return graph;\n    }\n}\n```\n\n**Python 3** (Thanks to @venetor for this Python 3 solution.)\n```\ndef minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n    adj = [[] for _ in range(n)]\n    for u, v in edges:\n        adj[u].append(v)\n        adj[v].append(u)\n\n    visited = set()\n    def dfs(node):\n        if node in visited:\n            return 0\n        visited.add(node)\n        secs = 0\n        for child in adj[node]:\n            secs += dfs(child)\n        if secs > 0:\n            return secs + 2\n        return 2 if hasApple[node] else 0\n\n    return max(dfs(0) - 2, 0)\n```\n
['C', 'Java', 'Python3']