1443.Minimum Time to Collect All Apples in a Tree

tags: Medium,Tree,DFS,BFS,Hash Table

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 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_i$,

$b_i$] means that exists an edge connecting the vertices

$a_i$ and

$b_i$. 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⁵
• edges.length == n - 1
• edges[i].length == 2
• 0 <=
  $a_i$ <
  $b_i$ <= n - 1
• $fro{m}_i$ <
  $t{o}_i$
• hasApple.length == n

解答

Javascript

function minTime(n, edges, hasApple) {
  const graph = new Array(n).fill(0).map(() => []);
  for (const [v1, v2] of edges) {
    graph[v1].push(v2);
    graph[v2].push(v1);
  }

  return dfs(0, -1, graph, hasApple);
}

function dfs(node, parent, graph, hasApple) {
  let totalTime = 0;
  let childTime = 0;
  for (const child of graph[node]) {
    if (child === parent) continue;
    childTime = dfs(child, node, graph, hasApple);
    if (childTime || hasApple[child]) {
      totalTime += childTime + 2;
    }
  }

  return totalTime;
}

參考官網的解答寫的，第一次寫直接做dfs掃過一遍把有遇到蘋果的距離直接乘2，忘記會重複計算，有夠蠢。
MarsgoatFeb 20, 2023

Reference

回到題目列表