Flip Operations
A tree of n nodes is an undirected connected graph Hnving (n - 1) edges. Given an undirected
tree comprising of tree_nodes number of nodes numbered from 0 to tree_nodes - 1, and rooted at
node 0. Each node has an initially binary value (0 or 1) represented by the array initial[], and an
expected binary value represented by the array expected[].
The following operation can be performed on the tree any number of times:
- Pick a node u and flip its value. Also, flip the value of all the nodes vin the subtree of u if v % 2 = u
%2. A node vlies in the subtree of u if ulies on the path from vto root. Flipping the value of a node
means flipping its binary value, i.e., from 0 to 1, and vice versa.
- The tree is represented by the arrays tree_from[] and tree_to[] where tree_from[i] is connected to
tree_to[i]via an edge for 0 ≤ i< tree_nodes - 1. Find the minimum number of operations needed
such that the final binary value of each node becomes equal to the array expected[].
Example
Consider the following:
tree_nodes = 4
initial = [1, 1, 0, 1]
expected = [0, 1, 1, 0]
tree_from = [0, 0, 1]
tree_to = [1, 2, 3]
The nodes are labeled <node number> :< value>.
Asked in:
No companies listed