[UVA] 13089 - Golden Coins

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 13089 - Golden Coins
Source            : UVA Online Judge
Category          : Graph Theory
Algorithm         : Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1000 + 5;
 
vector <int> graph[maxn];
int coin[maxn];
 
int dfs(int u, int p = -1, int depth = 0)
{
      int xor_sum = 0;
      if (coin[u] & 1) xor_sum ^= depth;
      for (int v : graph[u])
      {
            if (v == p) continue;
            xor_sum ^= dfs(v, u, depth + 1);
      }
      return xor_sum;
}
 
int main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int n;
            cin >> n;
            for (int i = 1; i <= n; i++) cin >> coin[i];
            for (int e = 1; e < n; e++)
            {
                  int u, v;
                  cin >> u >> v;
                  graph[u].emplace_back(v);
                  graph[v].emplace_back(u);
            }
            int ans = 0;
            for (int i = 1; i <= n; i++)
            {
                  if (dfs(i)) ++ans;
            }
            cout << "Case " << tcase << ": " << n-ans << endl;
            for (int i = 1; i <= n; i++) graph[i].clear();
      }
}