Very Easy PYTHON solution 95% #DFS, #With explanation
Intuition\nCount the number of parents that has children or grandchildren who has apples or they themselves has apples. \nFor example, if 6 node has apples or h
# Intuition\nCount the number of parents that has children or grandchildren who has apples or they themselves has apples. \nFor example, if 6 node has apples or has child / grandchild node that has apples answer is 6 * 2 - 2 = 10, we dont have to count the src node as it has travel cost of zero. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAs we have to find out if any children or grand children has apples, which requires to traverse the child node before the parent node, DFS is the best, easy and intuitive approach. \n\n# Complexity\n- Time complexity:\n$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n$$O(n^2)$$, the space to store the adjacency matrix. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        adj_mat: Dict[int, List[int]] = {}\n        for i in range(n):\n            adj_mat[i] = list()\n        \n        for u, v in edges:\n            adj_mat[u].append(v)\n            adj_mat[v].append(u)\n\n        visited = [False] * n\n\n        cost = [0]\n        def dfs(src):\n            have_child = False\n            visited[src] = True\n            for c in adj_mat[src]:\n                if not visited[c]:\n                    have_child = dfs(c) or have_child\n            if have_child or hasApple[src]:\n                cost[0] += 2\n            return have_child or hasApple[src]\n        dfs(0)\n        return 0 if cost[0] == 0 else cost[0] - 2\n\n```
['Python3']