3812. Minimum Edge Toggles on a Tree

SourceBiweekly Contest 174 Q4DifficultyHardRating2178

Description

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] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree.

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.

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'.

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.

If it is impossible to transform start into target, return an array containing a single element equal to -1.

Example 1:

Input: n = 3, edges = [[0,1],[1,2]], start = "010", target = "100"

Output: [0]

Explanation:

Toggle edge with index 0, which flips nodes 0 and 1.
The string changes from "010" to "100", matching the target.

Example 2:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]], start = "0011000", target = "0010001"

Output: [1,2,5]

Explanation:

Toggle edge with index 1, which flips nodes 1 and 2.
Toggle edge with index 2, which flips nodes 2 and 3.
Toggle edge with index 5, which flips nodes 1 and 6.

After these operations, the resulting string becomes "0010001", which matches the target.

Example 3:

Input: n = 2, edges = [[0,1]], start = "00", target = "01"

Output: [-1]

Explanation:

There is no sequence of edge toggles that transforms "00" into "01". Therefore, we return [-1].

Constraints:

2 <= n == start.length == target.length <= 10⁵
edges.length == n - 1
edges[i] = [a_i, b_i]
0 <= a_i, b_i < n
start[i] is either '0' or '1'.
target[i] is either '0' or '1'.
The input is generated such that edges represents a valid tree.

Solutions

Solution 1: DFS

Thinking

Toggling an edge flips both endpoints. \(n \le 10^5\) rules out subset search. On a tree the need inside a subtree is determined bottom-up.

A leaf that mismatches the target must toggle the edge to its parent, which then flips the parent's remaining need, so the demand travels upward.

DFS returns whether the subtree still needs the parent edge: each chosen child edge negates the current node's demand.

If the root still needs a flip, there is no solution; otherwise the sorted chosen edge indices form a shortest valid sequence.

We define an adjacency list \(g\) to represent the tree, where \(g[a]\) stores all adjacent nodes of node \(a\) and the indices of the corresponding edges.

We design a function \(\text{dfs}(a, \text{fa})\), which indicates whether the edge between node \(a\) and \(\text{fa}\) needs to be toggled in the subtree rooted at node \(a\) with parent \(\text{fa}\). The logic of the function \(\text{dfs}(a, \text{fa})\) is as follows:

Initialize a boolean variable \(\text{rev}\), indicating whether node \(a\) needs to be toggled. The initial value is \(\text{start}[a] \ne \text{target}[a]\).
Iterate through all adjacent nodes \(b\) of node \(a\) and the corresponding edge index \(i\):
- If \(b \ne \text{fa}\), recursively call \(\text{dfs}(b, a)\).
- If the recursive call returns true, it means the edge \([a, b]\) in the subtree needs to be toggled. We add the edge index \(i\) to the answer list and toggle \(\text{rev}\).
Return \(\text{rev}\).

Finally, we call \(\text{dfs}(0, -1)\). If the return value is true, it means it is impossible to convert \(\text{start}\) to \(\text{target}\), so we return \([-1]\). Otherwise, we sort the answer list and return it.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of nodes in the tree.

Python3JavaC++GoTypeScript

class Solution:
    def minimumFlips(
        self, n: int, edges: List[List[int]], start: str, target: str
    ) -> List[int]:
        g = [[] for _ in range(n)]
        for i, (a, b) in enumerate(edges):
            g[a].append((b, i))
            g[b].append((a, i))

        ans = []

        def dfs(a: int, fa: int) -> bool:
            rev = start[a] != target[a]
            for b, i in g[a]:
                if b != fa and dfs(b, a):
                    ans.append(i)
                    rev = not rev
            return rev

        if dfs(0, -1):
            return [-1]
        ans.sort()
        return ans

class Solution {
    private final List<Integer> ans = new ArrayList<>();
    private List<int[]>[] g;
    private char[] start;
    private char[] target;

    public List<Integer> minimumFlips(int n, int[][] edges, String start, String target) {
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 0; i < n - 1; ++i) {
            int a = edges[i][0], b = edges[i][1];
            g[a].add(new int[] {b, i});
            g[b].add(new int[] {a, i});
        }
        this.start = start.toCharArray();
        this.target = target.toCharArray();
        if (dfs(0, -1)) {
            return List.of(-1);
        }
        Collections.sort(ans);
        return ans;
    }

    private boolean dfs(int a, int fa) {
        boolean rev = start[a] != target[a];
        for (var e : g[a]) {
            int b = e[0], i = e[1];
            if (b != fa && dfs(b, a)) {
                ans.add(i);
                rev = !rev;
            }
        }
        return rev;
    }
}

class Solution {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<pair<int, int>> g[n];
        for (int i = 0; i < n - 1; ++i) {
            int a = edges[i][0], b = edges[i][1];
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        vector<int> ans;
        auto dfs = [&](this auto&& dfs, int a, int fa) -> bool {
            bool rev = start[a] != target[a];
            for (auto [b, i] : g[a]) {
                if (b != fa && dfs(b, a)) {
                    ans.push_back(i);
                    rev = !rev;
                }
            }
            return rev;
        };
        if (dfs(0, -1)) {
            return {-1};
        }
        ranges::sort(ans);
        return ans;
    }
};

func minimumFlips(n int, edges [][]int, start string, target string) []int {
    g := make([][]struct{ to, idx int }, n)
    for i := 0; i < n-1; i++ {
        a, b := edges[i][0], edges[i][1]
        g[a] = append(g[a], struct{ to, idx int }{b, i})
        g[b] = append(g[b], struct{ to, idx int }{a, i})
    }
    ans := []int{}
    var dfs func(a, fa int) bool
    dfs = func(a, fa int) bool {
        rev := start[a] != target[a]
        for _, p := range g[a] {
            b, i := p.to, p.idx
            if b != fa && dfs(b, a) {
                ans = append(ans, i)
                rev = !rev
            }
        }
        return rev
    }
    if dfs(0, -1) {
        return []int{-1}
    }
    sort.Ints(ans)
    return ans
}

function minimumFlips(n: number, edges: number[][], start: string, target: string): number[] {
    const g: number[][][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < n - 1; i++) {
        const [a, b] = edges[i];
        g[a].push([b, i]);
        g[b].push([a, i]);
    }
    const ans: number[] = [];
    const dfs = (a: number, fa: number): boolean => {
        let rev = start[a] !== target[a];
        for (const [b, i] of g[a]) {
            if (b !== fa && dfs(b, a)) {
                ans.push(i);
                rev = !rev;
            }
        }
        return rev;
    };
    if (dfs(0, -1)) {
        return [-1];
    }
    ans.sort((x, y) => x - y);
    return ans;
}

Solution 2: Explicit Stack

Thinking

Toggling an edge flips both endpoints. \(n\) can reach \(10^5\), so searching subsets of edges is impossible. On a chain the first recursive call always follows the only child, so the depth is \(n\) and exceeds the default recursion limit.

A leaf that mismatches the target must toggle the edge to its parent. That demand is known only after the whole subtree has been finished.

An explicit stack walks the tree in postorder. On entry, push the exit marker and then the children. On exit, start from whether the node differs from the target; each child edge that must be toggled negates that demand and is recorded.

If the root still needs a flip, there is no solution; otherwise the sorted chosen edge indices form a shortest valid sequence.

We define an adjacency list \(g\) to represent the tree, where \(g[a]\) stores all adjacent nodes of node \(a\) and the indices of the corresponding edges.

An explicit stack walks the tree from node \(0\) in postorder. Entering a node pushes that node's exit marker and then its children, so the children finish first. On exit, \(\text{rev}\) records whether the edge from the current node to its parent still needs a toggle. It starts as \(\text{start}[a] \ne \text{target}[a]\). For each child \(b\), if that subtree still needs the edge \([a, b]\) toggled, append the edge index \(i\) and negate \(\text{rev}\). The root has no parent. If the root's \(\text{rev}\) is still true, converting \(\text{start}\) to \(\text{target}\) is impossible and the result is \([-1]\). Otherwise sort the answer and return it.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of nodes in the tree.

Python3JavaC++GoTypeScript

class Solution:
    def minimumFlips(
        self, n: int, edges: List[List[int]], start: str, target: str
    ) -> List[int]:
        g = [[] for _ in range(n)]
        for i, (a, b) in enumerate(edges):
            g[a].append((b, i))
            g[b].append((a, i))
        ans = []
        need = [False] * n
        stk = [(0, -1, 0)]
        while stk:
            a, fa, state = stk.pop()
            if state == 0:
                stk.append((a, fa, 1))
                for b, _ in g[a]:
                    if b != fa:
                        stk.append((b, a, 0))
            else:
                rev = start[a] != target[a]
                for b, i in g[a]:
                    if b != fa and need[b]:
                        ans.append(i)
                        rev = not rev
                need[a] = rev
        if need[0]:
            return [-1]
        ans.sort()
        return ans

class Solution {
    public List<Integer> minimumFlips(int n, int[][] edges, String start, String target) {
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 0; i < n - 1; ++i) {
            int a = edges[i][0], b = edges[i][1];
            g[a].add(new int[] {b, i});
            g[b].add(new int[] {a, i});
        }
        List<Integer> ans = new ArrayList<>();
        boolean[] need = new boolean[n];
        Deque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[] {0, -1, 0});
        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            int a = cur[0], fa = cur[1], state = cur[2];
            if (state == 0) {
                stk.push(new int[] {a, fa, 1});
                for (var e : g[a]) {
                    int b = e[0];
                    if (b != fa) {
                        stk.push(new int[] {b, a, 0});
                    }
                }
            } else {
                boolean rev = start.charAt(a) != target.charAt(a);
                for (var e : g[a]) {
                    int b = e[0], i = e[1];
                    if (b != fa && need[b]) {
                        ans.add(i);
                        rev = !rev;
                    }
                }
                need[a] = rev;
            }
        }
        if (need[0]) {
            return List.of(-1);
        }
        Collections.sort(ans);
        return ans;
    }
}

class Solution {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; ++i) {
            int a = edges[i][0], b = edges[i][1];
            g[a].push_back({b, i});
            g[b].push_back({a, i});
        }
        vector<int> ans;
        vector<char> need(n);
        vector<array<int, 3>> stk{{0, -1, 0}};
        while (!stk.empty()) {
            auto cur = stk.back();
            stk.pop_back();
            int a = cur[0], fa = cur[1], state = cur[2];
            if (state == 0) {
                stk.push_back({a, fa, 1});
                for (auto [b, i] : g[a]) {
                    if (b != fa) {
                        stk.push_back({b, a, 0});
                    }
                }
            } else {
                bool rev = start[a] != target[a];
                for (auto [b, i] : g[a]) {
                    if (b != fa && need[b]) {
                        ans.push_back(i);
                        rev = !rev;
                    }
                }
                need[a] = rev;
            }
        }
        if (need[0]) {
            return {-1};
        }
        ranges::sort(ans);
        return ans;
    }
};

func minimumFlips(n int, edges [][]int, start string, target string) []int {
    g := make([][]struct{ to, idx int }, n)
    for i := 0; i < n-1; i++ {
        a, b := edges[i][0], edges[i][1]
        g[a] = append(g[a], struct{ to, idx int }{b, i})
        g[b] = append(g[b], struct{ to, idx int }{a, i})
    }
    ans := []int{}
    need := make([]bool, n)
    stk := [][3]int{{0, -1, 0}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        a, fa, state := cur[0], cur[1], cur[2]
        if state == 0 {
            stk = append(stk, [3]int{a, fa, 1})
            for _, p := range g[a] {
                if p.to != fa {
                    stk = append(stk, [3]int{p.to, a, 0})
                }
            }
        } else {
            rev := start[a] != target[a]
            for _, p := range g[a] {
                b, i := p.to, p.idx
                if b != fa && need[b] {
                    ans = append(ans, i)
                    rev = !rev
                }
            }
            need[a] = rev
        }
    }
    if need[0] {
        return []int{-1}
    }
    sort.Ints(ans)
    return ans
}

function minimumFlips(n: number, edges: number[][], start: string, target: string): number[] {
    const g: number[][][] = Array.from({ length: n }, () => []);
    for (let i = 0; i < n - 1; i++) {
        const [a, b] = edges[i];
        g[a].push([b, i]);
        g[b].push([a, i]);
    }
    const ans: number[] = [];
    const need: boolean[] = Array(n).fill(false);
    const stk: number[][] = [[0, -1, 0]];
    while (stk.length) {
        const [a, fa, state] = stk.pop()!;
        if (state === 0) {
            stk.push([a, fa, 1]);
            for (const [b] of g[a]) {
                if (b !== fa) {
                    stk.push([b, a, 0]);
                }
            }
        } else {
            let rev = start[a] !== target[a];
            for (const [b, i] of g[a]) {
                if (b !== fa && need[b]) {
                    ans.push(i);
                    rev = !rev;
                }
            }
            need[a] = rev;
        }
    }
    if (need[0]) {
        return [-1];
    }
    ans.sort((x, y) => x - y);
    return ans;
}

3812. Minimum Edge Toggles on a Tree

Description

Solutions

Solution 1: DFS

Solution 2: Explicit Stack

Comments