Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.The edges of the undirected tree are given in the array edges, where edges[i] = [a<sub>i</sub>, b<sub>i</sub>] means that exists an edge connecting the vertices a<sub>i</sub> and b<sub>i</sub>. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]Output: 8Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]Output: 6Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
class Solution: # Time: O(n) # Space: O(n) def min_time(self, n: int, edges: list[list[int]], has_apple: list[bool]) -> int: adj: list[list[int]] = [[] for _ in range(n)] for a, b in edges: adj[a].append(b) adj[b].append(a) seen = [False] * n parent = [-1] * n order = [0] seen[0] = True for u in order: for v in adj[u]: if not seen[v]: seen[v] = True parent[v] = u order.append(v) subtree_has_apple = list(has_apple) total = 0 for u in reversed(order): if u == 0: continue if subtree_has_apple[u]: total += 2 subtree_has_apple[parent[u]] = True return total
