Tap here to switch tabs
Problem
Submissions

Problem: Minimum Edge Toggles on a Tree

Try to solve the Minimum Edge Toggles on a Tree problem.

Statement

You are given an undirected tree with nn nodes labeled from 00 to n−1n - 1, represented by a 00 indexed 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] = [a_i, b_i] denotes an edge connecting nodes a_i and b_i.

You are also given two binary strings start and target, both of length nn, where each character represents the state of the corresponding node.

In one operation, you can toggle an edge with index ii, which flips the values of both nodes a_i and b_i from '$0$' to '$1$' or from '$1$' to '$0$'.

Return a list containing the indices of the edges that must be toggled to transform start into target. If there is no valid sequence of toggles, return [-1].

Constraints:

  • 2≤n==2 \leq n == start.length ==== target.length ≤105\leq 10^5

  • edges.length ==n−1== n - 1

  • edges[i] = [a_i, b_i]

  • 0≤ai,bi<n0 \leq 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.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Edge Toggles on a Tree

Try to solve the Minimum Edge Toggles on a Tree problem.

Statement

You are given an undirected tree with nn nodes labeled from 00 to n−1n - 1, represented by a 00 indexed 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] = [a_i, b_i] denotes an edge connecting nodes a_i and b_i.

You are also given two binary strings start and target, both of length nn, where each character represents the state of the corresponding node.

In one operation, you can toggle an edge with index ii, which flips the values of both nodes a_i and b_i from '$0$' to '$1$' or from '$1$' to '$0$'.

Return a list containing the indices of the edges that must be toggled to transform start into target. If there is no valid sequence of toggles, return [-1].

Constraints:

  • 2≤n==2 \leq n == start.length ==== target.length ≤105\leq 10^5

  • edges.length ==n−1== n - 1

  • edges[i] = [a_i, b_i]

  • 0≤ai,bi<n0 \leq 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.