FastPrep
Problem · Tree

Minimum Flips to Match Expected Binary Values in a Tree

● HardUkgOA

You are given an undirected tree with tree_nodes nodes, numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node initially has a binary value (0 or 1) given by the array initial[], and an expected binary value given by the array expected[].

You can perform the following operation any number of times:

Pick a node u and flip its value along with all nodes v in the subtree of u where v % 2 == u % 2. Flipping a value means toggling between 0 and 1.

Find the minimum number of operations needed so that the final binary values match expected[].

Examples
01 · Example 1
tree_nodes = 4
tree_from = [0, 0, 1]
tree_to = [1, 2, 3]
initial = [1, 1, 0, 1]
expected = [0, 1, 1, 0]
return = 2
Pick node 0 and flip it → initial = [0, 1, 1, 1] Pick node 3 and flip it → initial = [0, 1, 1, 0] (matches expected)
02 · Example 2
tree_nodes = 5
tree_from = [0, 1, 0, 1]
tree_to = [1, 2, 3, 4]
initial = [1, 0, 1, 1, 0]
expected = [1, 1, 0, 1, 1]
return = 3
:O
More Ukg problems
drafts saved locally
public int minimumFlipsToMatch(int tree_nodes, int[] tree_from, int[] tree_to, int[] initial, int[] expected) {
  // write your code here
}
tree_nodes4
tree_from[0, 0, 1]
tree_to[1, 2, 3]
initial[1, 1, 0, 1]
expected[0, 1, 1, 0]
expected2
sign in to submit