Minimum edge toggles on a tree

Tree Depth-First Search Graph Theory Topological Sort Sorting

68.8% acceptance

Mar 16, 2026

Undirected tree with n nodes. edges[i] = [ai, bi]. Binary strings start and target of length n. Operation: pick edge i, toggle both endpoints. Return array of edge indices (increasing order) to transform start into target. If impossible, return [-1].

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_flips(n: i32, edges: Vec<Vec<i32>>, start: String, target: String) -> Vec<i32> {
    let n = n as usize;
    let start: Vec<u8> = start.bytes().map(|b| b - b'0').collect();
    let target: Vec<u8> = target.bytes().map(|b| b - b'0').collect();

    let mut diff: Vec<u8> = vec![0; n];
    let mut total_diff = 0u32;
    for i in 0..n {
      diff[i] = start[i] ^ target[i];
      total_diff += diff[i] as u32;
    }

    // Each edge toggle flips 2 nodes, so total flips needed must be even
    if total_diff % 2 != 0 {
      return vec![-1];
    }

    if total_diff == 0 {
      return vec![];
    }

    // Build adjacency list with edge indices
    let mut adj = vec![vec![]; n];
    for (idx, e) in edges.iter().enumerate() {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u].push((v, idx));
      adj[v].push((u, idx));
    }

    // Root tree at 0, BFS order
    let mut parent = vec![0usize; n];
    let mut parent_edge = vec![0usize; n];
    let mut order = Vec::with_capacity(n);
    let mut visited = vec![false; n];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back(0);
    visited[0] = true;
    while let Some(u) = queue.pop_front() {
      order.push(u);
      for &(v, eidx) in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          parent[v] = u;
          parent_edge[v] = eidx;
          queue.push_back(v);
        }
      }
    }

    // Compute subtree diff count
    let mut subtree_diff = vec![0u32; n];
    for i in 0..n {
      subtree_diff[i] = diff[i] as u32;
    }
    for &u in order.iter().rev() {
      if u != 0 {
        subtree_diff[parent[u]] += subtree_diff[u];
      }
    }

    // Edge to child v is toggled iff subtree_diff[v] is odd
    let mut result = Vec::new();
    for &v in order.iter().skip(1) {
      if subtree_diff[v] % 2 == 1 {
        result.push(parent_edge[v] as i32);
      }
    }

    result.sort();
    result
  }
}