HackerEarth Tree and XOR problem solution

In this HackerEarth Tree and XOR problem solution For a tree X, rooted at node 1, having values at nodes, and a node i, lets define S(X,i) as the bitwise xor of all values in the subtree of node .

You are given a tree T. Let Ti be the tree remaining after removing all nodes in subtree of i. Define P(i) = max(j belongs to Ti) (S(T,i) xor S(Ti,j)). You have to find sum of P(i) over all nodes i!=1.

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

const int MAXN = 2e5 + 55;
int ar[MAXN], S[MAXN], tin[MAXN], tout[MAXN];
vector<int> START[MAXN], END[MAXN], adj[MAXN];
int POWER[55];
int timer = 0;
void DFS(int s, int par = -1) {
  tin[s] = ++timer;
  START[timer].push_back(s);
  S[s] = ar[s];
  for(auto it : adj[s]) {
    if(it == par) continue;
    DFS(it, s);
    S[s] ^= S[it];
  }
  tout[s] = timer;
  END[timer].push_back(s);
}
typedef struct node* pnode;
struct node {
  pnode L, R;
  node() {
    L = R = nullptr;
  }
};
pnode perL[MAXN], perR[MAXN];
int get(pnode root, int val, int lev) {
  if(lev == -1 or root == nullptr) return 0;
  int ret = 0;
  if(POWER[lev] & val) {
    if(root -> L != nullptr) return POWER[lev] + get(root -> L, val, lev - 1);
    else {
      return get(root -> R, val, lev - 1);
    }

  }
  else {
    if(root -> R != nullptr) return POWER[lev] + get(root -> R, val, lev - 1);
    else {
      return get(root -> L, val, lev - 1);
    }
  }
}
int getLeft(int idx, int val) {
  if(idx < 1) return 0;
  return get(perL[idx], val, 29);
}
int n;
int getRight(int idx, int val) {
  if(idx > n) return 0;
  return get(perR[idx], val, 29);
}
long long answer = 0;
void dfs(int s, int XOR = 0, int par = -1) {
  for(auto it : adj[s]) {
    if(it == par) continue;
    dfs(it, max(XOR, S[s]), s);
  }
  if(s != 1) {
    int ans = XOR;
    ans = max(ans, getLeft(tin[s] - 1, S[s]));
    ans = max(ans, getRight(tout[s] + 1, S[s]));
    answer += 1LL * ans;
  }
}
pnode insert(pnode root, pnode other, int val, int lev) {
  if(lev == -1) return root;
  if(POWER[lev] & val) {
    if(other == nullptr) {
      root -> R = new node();
      root -> R = insert(root -> R, other, val, lev - 1);
    }
    else {
      root -> L = other -> L;
      other = other -> R;
      root -> R = new node();
      root -> R = insert(root -> R, other, val, lev - 1);
    }
  }
  else {
    if(other == nullptr) {
      root -> L = new node();
      root -> L = insert(root -> L, other, val, lev - 1);
    }
    else {
      root -> R = other -> R;
      other = other -> L;
      root -> L = new node();
      root -> L = insert(root -> L, other, val, lev - 1);
    }
  }
  return root;
}
void process() {
  perL[0] = new node();
  for(int i = 1; i <= n; i++) {
    perL[i] = new node();
    perL[i] -> L = perL[i - 1] -> L;
    perL[i] -> R = perL[i - 1] -> R;
    for(int it = 0; it < (int)END[i].size(); it++) {
      int node = END[i][it];
      if(it == 0) perL[i] = insert(perL[i], perL[i - 1], S[node], 29);
      else perL[i] = insert(perL[i], perL[i], S[node], 29);
    }
  }
  perR[n + 1] = new node();
  for(int i = n; i >= 1; i--) {
    perR[i] = new node();
    perR[i] -> L = perR[i + 1] -> L;
    perR[i] -> R = perR[i + 1] -> R;
    assert((int)START[i].size() <= 1);
    for(int it = 0; it < (int)START[i].size(); it++) {
      int node = START[i][it];
      perR[i] = insert(perR[i], perR[i + 1], S[node], 29);
    }
  }
}
int main() {
  POWER[0] = 1;
  for(int i = 1; i < 35; i++) POWER[i] = POWER[i - 1] << 1;
  cin >> n;
  assert(n >= 1 and n <= 200000);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &ar[i]);
    assert(ar[i] >= 1 and ar[i] <= 1000000000);
  }
  for(int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    assert(x != y and x >= 1 and x <= n and y >= 1 and y <= n);
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  DFS(1);
  process();
  dfs(1);
  cout << answer << endl;
  return 0;
}