1709E - XOR Tree - CodeForces Solution

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

// template <typename T>
// using ordered_multiset = tree<T, null_type, less_equal<T>,
// 			      rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;

using pii = pair<int, int>;
#define mp make_pair
#define xx first
#define yy second

#define pb emplace_back
#define sz(x) int(x.size())

const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;

set<ll> dp[N];
vector<int> graph[N];
ll a[N], b[N];

void dfs(int u, int par, int &ret) {
  b[u] = (par == -1) ? b[par] : (b[par] ^ a[u]);
  dp[u].insert(b[u]);

  bool change = false;

  for (int v : graph[u]) {
    if (v == par) continue;
    dfs(v, u, ret);

    if (sz(dp[u]) < sz(dp[v]))
      swap(dp[u], dp[v]);
    
    for (int x : dp[v])
      if (dp[u].count(x ^ a[u]))
	change = true;

    for (int x : dp[v])
      dp[u].insert(x);
  }
 
  if (change) {
    ++ret;
    dp[u].clear();
  }
}

void solve() {
  int n;
  cin >> n;

  for (int i = 0; i < n; ++i)
    cin >> a[i];
  
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    graph[u].pb(v);
    graph[v].pb(u);
  }

  int ret = 0;
  dfs(0, -1, ret);
  cout << ret << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}