1443. Minimum Time to Collect All Apples in a Tree

https://leetcode.com/problems/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:

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:

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。

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)