429A. Xor - Codeforces Solution C++

➤  Problem Link : 429A. Xor 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

vector<int> adj[100001];
vector<int> init,goal;

int cnt=0;
vector<int> ans;
void dfs(int i,int lvl,bool zf,bool of,int p)
{
	if(lvl==0)
	{
		if(zf)
			init[i]=init[i]^1;

		if(init[i]!=goal[i])
		{
			cnt++;
			zf=zf^1;
			ans.push_back(i);
		}
	}
	else
	{
		if(of)
			init[i]=init[i]^1;
		if(init[i]!=goal[i])
		{
			cnt++;
			of=of^1;
			ans.push_back(i);
		}
	}
	for(int j=0;j<adj[i].size();j++)
	{
		if(adj[i][j]==p)
			continue;
		dfs(adj[i][j],lvl^1,zf,of,i);
	}


}

int main()
{
	int n,u,v,a;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	init.push_back(0);
	goal.push_back(0);
	for(int i=0;i<n;i++)
	{
		cin>>a;
		init.push_back(a);
	}
	for(int i=0;i<n;i++)
	{
		cin>>a;
		goal.push_back(a);
	}

	cnt=0;
	dfs(1,0,0,0,-1);
	cout<<cnt<<"\n";
	for(auto it : ans)
	    cout<<it<<"\n";


}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.