> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/1443.-minimum-time-to-collect-all-apples-in-a-tree.md).

# 1443. Minimum Time to Collect All Apples in a Tree

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 in order 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] = [fromi, toi]` means that exists an edge connecting the vertices `fromi` and `toi`. 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.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_1.png)

```
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: 8 
Explanation: 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.  
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_2.png)

```
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: 6
Explanation: 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.  
```

**Example 3:**

```
Input: 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
```

**Constraints:**

* `1 <= n <= 10^5`
* `edges.length == n-1`
* `edges[i].length == 2`
* `0 <= fromi, toi <= n-1`
* `fromi < toi`
* `hasApple.length == n`

树的结点由\[0, n)表示，edges数组指定了树的形状，hasApple指定哪些结点有apple，计算从root(0号结点)开始拿到所有apple并返回root所需的最少步数。根据edge把每个结点的children建立起来，再从root开始分治处理每个child并让它们返回从该child点开始取到所有apple并回到该结点所需的最少步数。当子节点结果的和为0且当前结点也不含apple时，意味着该子树是多余的，返回0。否则返回子节点结果和并当该结点不是root时再额外加上2。

```python
class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        v = collections.defaultdict(list)
        for f, t in edges:
            v[f].append(t)
        def dfs(node):
            res = 0
            for i in v[node]:
                res += dfs(i)
            if res == 0:
                return 2 if hasApple[node] else 0
            return res + (2 if node != 0 else 0)
        return dfs(0)
        
        
```