Minimum flips to match target values in a rooted tree

Imagine a rooted tree ( with root as node 1). Every node is given two values, init value and expected value. Our task is to flip the node value to make the init equalize expected given the condition that changing any node (which is at say level L) value will force us to flip the value of all its child nodes at level L+2, L+4, L+6 and so on. We need to output the minimum number of operations to do so with the node numbers whose values we are flipping.

If we have the above tree, then filpping the value of node 2, will result in flipping the value of nodes 6 and 9.

Examples :

Input :
10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
Output :
2
4
7
Explanation :
Change value at node 4 first, and then of node 7.

To understand the problem, notice that when we fix any node, all it’s ancestors should be fixed i.e. we need to move from top to down. Lets assume we move from bottom to up, there exists a path u->v->w. We fix w, but then we reach upwards and fix u. Fixing u will cause value of node w to change again(and thus further children of w), hence, increasing the number of fix operations. Thus, we need to ensure all the ancestors of a node are fixed when we try to fix it, if needed. This is the only way to get minimum number of fix operations. Approach of this will hence be, apply dfs and for any node you do a fix, update the value of the children at alternate levels from the current level. This gives us an O(n^2) approach. Hence, we’ll try optimizing it. Suppose, you are at some node. How to know its final value after updates are made to all its ancestors? This is where we need to have two variables – evenChange and odChange in our recursive calls. evenChange denotes number of changes made at all even ancestral levels of currNodes and similarly for oddChange. Example, if our tree is like: (a->b) denotes initial and expected value for any node respectively. 1 (0->1) // level 0 / 2 (1->1) // level 1 / 3 (0->1) // level 2 We make change at node 1 and increase the evenChange (=1) and oddChange remains 0. We come at node 2, no fix is required, variables remains unchanged. We reach node 3 (even level), we see evenchange is 1, which denotes there was change in some ancestor of this node which will cause value of node 3 to change. Thus, the finalValue of node3 can be easily calculated by taking mod of evenChange (or oddChange) with 2. This way we get the finalvalue of node 3 in constant time. Take some to analyze and then look at the below code.

#include <iostream>
#include<vector>
using namespace std;

#define MAX 100001

int n;
int ans = 0;
int in[MAX];
int expected[MAX];
bool isCh[MAX];
vector<int>vec[MAX];

void dfs ( int currNode, int parentNode, int currLevel, int evenChange, int oddChange) {
	
	int finalVal;
	int levChange=0;
	
	
	if ( currLevel %2 == 0 ) {
		finalVal = evenChange%2;
	}
	else {
		finalVal = oddChange%2;
	}
	
	
	if ( finalVal == 0 )
		finalVal = in[currNode];
	else
		finalVal = 1- in[currNode];
	
	if ( finalVal != expected[currNode] ) {
		ans++;
		isCh[currNode] = 1;
		levChange=1; // make a fix here
	}else {
		levChange  = 0;
	}
	
	for ( int i=0; i<vec[currNode].size(); i++ ) {
		int dest = vec[currNode][i];
		
		if ( dest != parentNode ) {
			
			if ( currLevel %2 == 0 ) {
				// even level
				dfs(dest, currNode,currLevel+1,evenChange+levChange, oddChange);
			}
			else {
				// odd level
				dfs(dest, currNode,currLevel+1,evenChange, oddChange +levChange);
			}
		}
	}
}

int main() {
	// your code goes here
	
	cin>>n;
	
	int i,a,b;
	
	for ( i=0; i<n-1; i++ ) {
		cin>>a>>b;
		
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	
	for ( i=1; i<=n; i++ ) {
		cin>>in[i];
	}
	
	for ( i=1; i<=n; i++ ) {
		cin>>expected[i];
	}
	
	
	dfs(1,-1,0,0,0);
	
	cout << ans << endl;
	
	for ( i=1; i<=n; i++ ) {
		if ( isCh[i] == 1)
			cout << i << endl;
	}
	
	return 0;
}

Input : 10 2 1 3 1 4 2 5 1 6 2 7 5 8 6 9 8 10 5 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 Output: 2 4 7