2603. Collect Coins in a Tree Hard

1/**
2 * [2603] Collect Coins in a Tree
3 *
4 * There exists an undirected and unrooted tree with n nodes indexed from 0 to n - 1. You are given an integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an array coins of size n where coins[i] can be either 0 or 1, where 1 indicates the presence of a coin in the vertex i.
5 * Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times: 
6 * 
7 * 	Collect all the coins that are at a distance of at most 2 from the current vertex, or
8 * 	Move to any adjacent vertex in the tree.
9 * 
10 * Find the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex.
11 * Note that if you pass an edge several times, you need to count it into the answer several times.
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2023/03/01/graph-2.png" style="width: 522px; height: 522px;" />
15 * Input: coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
16 * Output: 2
17 * Explanation: Start at vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 2.
18 * 
19 * <strong class="example">Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2023/03/02/graph-4.png" style="width: 522px; height: 522px;" />
21 * Input: coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
22 * Output: 2
23 * Explanation: Start at vertex 0, collect the coins at vertices 4 and 3, move to vertex 2,  collect the coin at vertex 7, then move back to vertex 0.
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	n == coins.length
29 * 	1 <= n <= 3 * 10^4
30 * 	0 <= coins[i] <= 1
31 * 	edges.length == n - 1
32 * 	edges[i].length == 2
33 * 	0 <= ai, bi < n
34 * 	ai != bi
35 * 	edges represents a valid tree.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/collect-coins-in-a-tree/
41// discuss: https://leetcode.com/problems/collect-coins-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn collect_the_coins(coins: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2603() {
59    }
60}
61