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^5edges.length == n-1edges[i].length == 20 <= fromi, toi <= n-1fromi < toihasApple.length == n
Solution: DFS
Build the graph (tree) and DFS.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) { vector<vector<int>> g(n); for (const auto& e : edges) g[e[0]].push_back(e[1]); function<int(int)> dfs = [&] (int cur) { int total = 0; for (int nxt : g[cur]) { int cost = dfs(nxt); if (cost > 0 || hasApple[nxt]) total += 2 + cost; } return total; }; return dfs(0); } }; |
if edge is not ordered
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) { vector<vector<int>> g(n); for (const auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); } vector<int> seen(n); function<int(int)> dfs = [&] (int cur) { seen[cur] = 1; int total = 0; for (int child : g[cur]) { if (seen[child]) continue; int cost = dfs(child); if (cost > 0 || hasApple[child]) total += 2 + cost; } return total; }; return dfs(0); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment