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

1/**
2 * [1443] Minimum Time to Collect All Apples in a Tree
3 *
4 * 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.
5 * The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_1.png" style="width: 300px; height: 212px;" />
9 * Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
10 * Output: 8 
11 * 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.  
12 * 
13 * Example 2:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/min_time_collect_apple_2.png" style="width: 300px; height: 212px;" />
15 * Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
16 * Output: 6
17 * 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.  
18 * 
19 * Example 3:
20 * 
21 * Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
22 * Output: 0
23 * 
24 *  
25 * Constraints:
26 * 
27 * 	1 <= n <= 10^5
28 * 	edges.length == n - 1
29 * 	edges[i].length == 2
30 * 	0 <= ai < bi <= n - 1
31 * 	fromi < toi
32 * 	hasApple.length == n
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/
38// discuss: https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn min_time(n: i32, edges: Vec<Vec<i32>>, has_apple: Vec<bool>) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_1443() {
56    }
57}
58