[Codeforces] Xor-tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Xor-tree
Source            : Spoj
Category          : Graph Theory, Tree
Algorithm         : Tree, DFS
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
vector <int> graph[maxn];
int initial_val[maxn];
int goal[maxn];
int level[maxn];
bitset <maxn> take;
 
inline void dfs(int u = 1, int p = -1, int flipEven = 0, int flipOdd = 0)
{
      for (int v : graph[u])
      {
            if (v == p) continue;
            level[v] = level[u] + 1;
            if (~level[v] & 1)
            {
                  if (flipEven) initial_val[v] ^= 1;
                  if (initial_val[v] != goal[v])
                  {
                        take.set(v);
                        initial_val[v] ^= 1;
                        dfs(v, u, flipEven ^ 1, flipOdd);
                  }
                  else
                  {
                        dfs(v, u, flipEven, flipOdd);
                  }
            }
            else
            {
                  if (flipOdd) initial_val[v] ^= 1;
                  if (initial_val[v] != goal[v])
                  {
                        take.set(v);
                        initial_val[v] ^= 1;
                        dfs(v, u, flipEven, flipOdd ^ 1);
                  }
                  else
                  {
                        dfs(v, u, flipEven, flipOdd);
                  }
            }
      }
}
 
int main()
{
      freopen("in.txt", "r", stdin);
 
      int tnode;
      cin >> tnode;
      for (int i = 1; i < tnode; i++)
      {
            int u, v;
            cin >> u >> v;
            graph[u].emplace_back(v);
            graph[v].emplace_back(u);
      }
      for (int i = 1; i <= tnode; i++) cin >> initial_val[i];
      for (int i = 1; i <= tnode; i++) cin >> goal[i];
      level[1] = 1;
      if (initial_val[1] != goal[1])
      {
            take.set(1);
            dfs(1, -1, 0, 1);
      }
      else dfs();
      cout << take.count() << "\n";
      for (int i = 1; i <= tnode; i++) if (take.test(i)) cout << i << "\n";
}