🧑‍🏫 [Java] | Full Solution Explanation [Article]
Intuition\nThe question asks to return the minimum time that it takes to walk to reach all apple trees. We can rephrase it as the minimum edges (travel cost) to
# Intuition\nThe question asks to return the minimum time that it takes to walk to reach all apple trees. We can rephrase it as the minimum edges (travel cost) to reach all the apple trees and back to the root.\n\nThe initial intuition may be to use a BFS, but BFS falls short for this problem because we also need to calculate the distance between the apple nodes themself. Basically, BFS will let us know that we found two apple trees at distances `x` and `y` from the root, but we can\'t easily calculate how much it takes to walk from `x` to `y` traversing all the edges of the tree.\n\nThe path we need to calculate should consider walking *to* to the apple tree and *back* from it. This is exactly how DFS works, so we need to apply it. But how?\n\nWe need to observe that if we are located at some node `n`, we don\'t need to calculate the travel path for the edges below it if none contain an apple tree. But, conversely, if the nodes below do contain an apple tree, we must calculate the edges it takes to *reach it*, and the edges *back from it*.\n\nSo we have two important phases in our algorithm, the traversal logic and the return logic, which means what we communicate upwards in the call stack.\n\nFor the return logic, we must add `+1` to the `travelCost `(initialized at 0 for every node) if it contains an apple or there is an apple below it. This way we don\'t miss on upstream edges containing an apple.\n\nFor the traversal logic, we must add +1 to the return type of the child if it contains an apple, because we need to include the downstream edge when it contains an apple.\n\nNow this will form the recurrence transition to solve the problem. Note that we need to subtract -1 from the root call of the recursion because we return +1, and it should be omitted for the first call.\n\n\n\n# Code\n```\n    class Solution {\n        public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n            Map<Integer, List<Integer>> graph = new HashMap<>();\n            for (int i = 0; i < n; i++) {\n                graph.put(i, new ArrayList<>());\n            }\n\n            for (int[] edge : edges) {\n                graph.get(edge[0]).add(edge[1]);\n                graph.get(edge[1]).add(edge[0]);\n            }\n\n            return Math.max(0, calculateTravel(graph, -1, 0, hasApple) - 1); // -1 because the return value is +1\n        }\n\n        private int calculateTravel(Map<Integer, List<Integer>> graph, int parent, int node, List<Boolean> hasApple) {\n            int travelCost = 0;\n\n            for (int child : graph.get(node)) {\n                if (child == parent) continue;\n\n                int childTravelCost = calculateTravel(graph, node, child, hasApple);\n                if (childTravelCost != 0) {\n                    travelCost += childTravelCost + 1; // +1 because I go down\n                }\n            }\n            return (travelCost == 0 && !hasApple.get(node)) ? 0 : travelCost + 1;\n\n\n        }\n    }\n```
['Java']