3812. Minimum Edge Toggles on a Tree Hard

1/**
2 * [3812] Minimum Edge Toggles on a Tree
3 *
4 * You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by 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.
5 * You are also given two binary strings start and target of length n. For each node x, start[x] is its initial color and target[x] is its desired color.
6 * In one operation, you may pick an edge with index i and toggle both of its endpoints. That is, if the edge is [u, v], then the colors of nodes u and v each flip from '0' to '1' or from '1' to '0'.
7 * Return an array of edge indices whose operations transform start into target. Among all valid sequences with minimum possible length, return the edge indices in increasing​​​​​​​ order.
8 * If it is impossible to transform start into target, return an array containing a single element equal to -1.
9 *  
10 * <strong class="example">Example 1:
11 * <strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2025/12/18/example1.png" style="width: 271px; height: 51px;" />​​​​​​​
12 * <div class="example-block">
13 * Input: <span class="example-io">n = 3, edges = [[0,1],[1,2]], start = "010", target = "100"</span>
14 * Output: <span class="example-io">[0]</span>
15 * Explanation:
16 * Toggle edge with index 0, which flips nodes 0 and 1.<br />
17 * ​​​​​​​The string changes from "010" to "100", matching the target.
18 * </div>
19 * <strong class="example">Example 2:
20 * <strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2025/12/18/example2.png" style="width: 411px; height: 208px;" />
21 * <div class="example-block">
22 * Input: <span class="example-io">n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]], start = "0011000", target = "0010001"</span>
23 * Output: <span class="example-io">[1,2,5]</span>
24 * Explanation:
25 * 
26 * 	Toggle edge with index 1, which flips nodes 1 and 2.
27 * 	Toggle edge with index 2, which flips nodes 2 and 3.
28 * 	Toggle edge with index 5, which flips nodes 1 and 6.
29 * 
30 * After these operations, the resulting string becomes "0010001", which matches the target.
31 * </div>
32 * <strong class="example">Example 3:
33 * <strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2025/12/18/example3.png" style="width: 161px; height: 51px;" />​​​​​​​
34 * <div class="example-block">
35 * Input: <span class="example-io">n = 2, edges = [[0,1]], start = "00", target = "01"</span>
36 * Output: <span class="example-io">[-1]</span>
37 * Explanation:
38 * There is no sequence of edge toggles that transforms "00" into "01". Therefore, we return [-1].
39 * </div>
40 *  
41 * Constraints:
42 * 
43 * 	2 <= n == start.length == target.length <= 10^5
44 * 	edges.length == n - 1
45 * 	edges[i] = [ai, bi]
46 * 	0 <= ai, bi < n
47 * 	start[i] is either '0' or '1'.
48 * 	target[i] is either '0' or '1'.
49 * 	The input is generated such that edges represents a valid tree.
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/minimum-edge-toggles-on-a-tree/
55// discuss: https://leetcode.com/problems/minimum-edge-toggles-on-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn minimum_flips(n: i32, edges: Vec<Vec<i32>>, start: String, target: String) -> Vec<i32> {
61        vec![]
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3812() {
73    }
74}
75