发表于 2024.08.22

• 不难得知，如果一个子树中没有苹果可摘，那么就没必要经过；否则，进去和出来都要花费2个单位时间(指的是进去和离开这个子树的用时，不包括内部的采摘时间)。因此，我们可以使用DFS进行后序遍历，递归计算每个子树所需的采摘时间。如果子树中至少一个子树有苹果可摘(即返回值不为0)，或者当前子树的根节点有苹果，则消耗时间为2 + 所有子树的采摘时间；否则，消耗时间为0。最后，返回从根节点出发的总采摘时间即可。

  需要注意的是，对于根节点，没必要+2，因为根节点作为起点，不需要进入。

  class Solution:
      def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
          adj_list = [[] for _ in range(n)]
          for u, v in edges:
              adj_list[u].append(v)
              adj_list[v].append(u)
  
          def dfs(cur: int, pa: int):
              res = 0
              for child in adj_list[cur]:
                  if child == pa:
                      continue
                  res += dfs(child, cur)
              # 判断当前子树是否需要进去采摘，如果需要，根据其是否为根节点，加上进出的时间
              # 根节点不需要+2，非根节点中，自身有苹果`hasApple[cur] == True`或者子树有苹果`res > 0`，需要进去采摘
              if (hasApple[cur] or res) and cur != 0:  
                  res += 2
              return res
  
          return dfs(0, -1)

• LC 题目链接