You are given an undirected tree consisting of n
vertices numbered from 0
to n-1
. Some vertices have apples. You start at vertex 0 and need to collect all apples and return to vertex 0. It takes 1 second to walk over one edge. Find the minimum time to collect all apples.
The edges of the tree are given in the array edges
, where edges[i] = [a_i, b_i]
indicates an edge between vertices a_i
and b_i
. The boolean array hasApple
indicates whether a vertex has an apple (hasApple[i] = true
if vertex i
has an apple, otherwise false
).
Example 1:
n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8
Example 2:
n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Example 3:
n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0
Explain your approach and provide code.
A brute-force approach would involve exploring all possible paths from vertex 0, collecting apples along the way, and returning to vertex 0. This approach would be highly inefficient, especially for larger trees, as it would involve redundant calculations and exploring paths that don't necessarily lead to any apples.
The optimal approach utilizes Depth-First Search (DFS) to traverse the tree. The key idea is to recursively explore the tree, and for each subtree, determine if it's worth visiting (i.e., if it contains any apples, either directly or in its subtrees). If a subtree contains an apple, the cost of traversing that subtree (twice the edge weight to enter and exit) is added to the total time. The algorithm starts at vertex 0 and explores the tree.
edges
.subtree_cost
to 0.subtree_cost
.subtree_cost
is greater than 0 (meaning there are apples in the subtree), add 2 to the subtree_cost
(representing the cost of entering and exiting the current node's edge).subtree_cost
.def minTime(n: int, edges: list[list[int]], hasApple: list[bool]) -> int:
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
def dfs(node: int, parent: int) -> int:
subtree_cost = 0
for neighbor in adj[node]:
if neighbor != parent:
cost = dfs(neighbor, node)
subtree_cost += cost
if (hasApple[node] or subtree_cost > 0) and parent != -1:
subtree_cost += 2
return subtree_cost
result = dfs(0, -1)
return max(0, result)