Clean Python 3, peel onion in O(N), 100% time/space
Just like performing Kahn\'s algorithm of topological sort on a tree.\nSum degrees of each node first, then peel the tree from those nodes whose degree is 1.\nO
Just like performing Kahn\'s algorithm of topological sort on a tree.\nSum degrees of each node first, then peel the tree from those nodes whose degree is 1.\nOnce there is no appropriate node can be removed, just return sum of all degrees.\nNote that we shouldn\'t peel node `0` so let `hasApple[0] = True` at beginning.\nTime: `O(N)`\nEach edge will be visited at most twice, and there will be n - 1 edges because it\'s a tree.\nSpace: `O(N)`\n```\nimport collections\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        hasApple[0], degree = True, [0] * n\n        graph = collections.defaultdict(list)\n        for u, v in edges:\n            graph[u].append(v)\n            graph[v].append(u)\n            degree[u] += 1\n            degree[v] += 1\n        queue = collections.deque(v for v in range(n) if degree[v] == 1)\n        while queue:\n            u = queue.popleft()\n            if hasApple[u]: continue\n            for v in graph[u]:\n                if degree[v] > 0:\n                    degree[v] -= 1\n                    degree[u] -= 1\n                    if degree[v] == 1:\n                        queue.append(v)\n        return sum(degree)\n```\n\n--\nAnother way to solve this problem is to propagate the nodes which have apples:\n```\nimport collections\nclass Solution:\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        def dfs(node: int, prev: int) -> bool:\n            for neighbor in graph[node]:\n                if neighbor != prev and dfs(neighbor, node):\n                    hasApple[node] = True\n            return hasApple[node]\n\n        graph = collections.defaultdict(list)\n        for u, v in edges:\n            graph[u].append(v)\n            graph[v].append(u)\n        dfs(0, -1)\n        return (sum(hasApple) - hasApple[0]) * 2\n```\n
[]