1878G - wxhtzdy ORO Tree - CodeForces Solution

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

const int B = 3;

struct node {
  int a[2 * B];
  int len;

  node() {
    for (int i = 0; i < B; i++) {
      a[i] = 1e9;
      a[B + i] = -1e9;
    }
    len = 1;
  }

  node(const node & t) {
    for (int i = 0; i < B; i++) {
      a[i] = t.a[i];
      a[B + i] = t.a[B + i];
    }
    len = t.len;
  }

  node(int x) {
    for (int i = 0; i < B; i++) {
      a[i] = 1e9;
      a[B + i] = -1e9;
      if ((x >> i) & 1) {
        a[i] = 0;
        a[B + i] = 0;
      }
    }
    this->len = 1;
  }

	// NOT COMMUTATIVE
	node operator+(node const & b) {
    node ret = node();
    ret.len = len + b.len;
    for (int i = 0; i < B; i++) {
      ret.a[i] = min(b.a[i] + len, a[i]);
      ret.a[B + i] = max(len + b.a[B + i], this->a[B + i]);
    }
		return ret;
	}

	node reverse() {
		node ret = node();
    ret.len = len;
    for (int i = 0; i < B; i++) {
      if (a[B + i] > -1e8) {
        ret.a[i] = len - a[B + i] - 1;
      } else {
        ret.a[i] = 1e9;
      }
      if (a[i] < 1e8) {
        ret.a[B + i] = len - a[i] - 1;
      } else {
        ret.a[B + i] = -1e9;
      }
    }
		return ret;
	}
};


template<class T>
struct LCA {
	T ID;
	bool online = false;
	const int LEVELS = 18;
	vector<vector<int > > v;
	vector<int> depth;
	vector<T> a;
	vector<vector<pair<int, T> > > jump;
	vector<pair<int, int> > euler_tour;

	void getDepth(int x, int last) {
		if (last != -1) depth[x] = depth[last] + 1;
		for (int n : v[x]) {
			if (last == n) continue;
			getDepth(n, x);
		}
	}
	
	explicit LCA(vector<vector<int> > & _v, vector<T> & _a, T _ID = T()) : ID(_ID) {
		v = _v;
		a = _a;

		int n = v.size();
		depth.assign(n, 0);
		jump.resize(LEVELS);

		for (int i = 0; i < LEVELS; i++) {
			jump[i].assign(n, {-1, ID});
		}
		euler_tour.resize(n);
		getDepth(0, -1);

		int cnt = 0;
		// populate jump[i] with the 2^0th ancestor of i, and d with the euler

		function<void (int x, int & cnt, int last)> lca_dfs = [&](int x, int & cnt, int last) {
			jump[0][x] = {last, a[x]};
			int s = cnt;
			for (auto u : v[x]) {
				if (u == last) continue;
				lca_dfs(u, ++cnt, x);
			}
			int e = cnt;
			euler_tour[x] = {s, e};
		};

		lca_dfs(0, cnt, -1);

		update_jump();
	}
  void update_jump() {
    for (int i = 1; i < jump.size(); i++) {
			for (int j = 0; j < jump[i].size(); j++) {
				auto old = jump[i - 1][j];
				if (old.first == -1) continue;
				auto next = jump[i - 1][old.first];
				jump[i][j] = {next.first, old.second + next.second};
			}
		}
  }

	void addEdge(int x, int y, T w) {
		online = true;
		if (y >= a.size()) {
			assert(y == a.size());
			a.push_back(w);
			v.push_back({x});
			depth.push_back(depth[x] + 1);
			for (int i = 0; i < jump.size(); i++) {
				jump[i].push_back({});
			}
		}
		a[y] = w;
		v[y] = {x};
		depth[y] = depth[x] + 1;
		v[x].push_back(y);
		jump[0][y] = {x, w};
		for (int i = 1; i < jump.size(); i++) {
			auto old = jump[i - 1][y];
			if (old.first == -1) continue;
			auto next = jump[i - 1][old.first];
			jump[i][y] = {next.first, old.second + next.second};
		}
	}

	// return if a is an ancestor of b. This runs in log(n)
	bool isAncestorOnline(int a, int b) {
		if (depth[b] < depth[a]) return false;
		return jmp(b, depth[b] - depth[a]).first == a;
	}

	// runs in constant time
	bool isAncestorOffline(int a, int b) {
		return (euler_tour[a].first <= euler_tour[b].first && euler_tour[a].second >= euler_tour[b].second);
	}

	// THIS IS LOG^2(n) if edges are added online and LOG(n) otherwise.
	T query(int x, int y) {
		int anc = lca(x, y);
		auto xa = jmp(x, depth[x] - depth[anc]).second + a[anc];
		auto xb = jmp(y, depth[y] - depth[anc]).second.reverse();
		return xa + xb;
	}

	bool isAncestor(int a, int b) {
		if (online) {
			return isAncestorOnline(a, b);
		}
		return isAncestorOffline(a, b);
	}

	// jumps to the dth ancestor of x
	// returns the ancestor with the answer on a segment (NOT INCLUDING LAST NODE)
	pair<int, T> jmp(int x, int d) {
		pair<int, T> ret = {x, ID};
		for (int i = 0; i < LEVELS; i++) {
			if ((1 << i) & d) {
				ret = {jump[i][x].first, ret.second + jump[i][x].second};
				x = ret.first;
			}
			if (x == -1) return {-1, ID};
		}
		return ret;
	}

	int lca(int a, int b) {
		int low = 0;
		int high = 1 << LEVELS;
		int best = -1;
    
		while (low <= high) {
			int mid = (low + high) / 2;
			auto anc = jmp(a, mid);
			if (anc.first == -1) {
				high = mid - 1;
				continue;
			}
			if (isAncestor(anc.first, b)) {
				high = mid - 1;
				best = anc.first;
			} else {
				low = mid + 1;
			}
		}
		return best;
	}
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests;
  cin >> tests;
  for (int test = 1; test <= tests; test++) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i< n; i++) cin >> a[i];
    vector<vector<int> > v(n);
    for (int i = 0; i < n - 1; i++) {
      int x, y;
      cin >> x >> y;
      x--;
      y--;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    int qq;
    cin >> qq;
    vector<pair<int, int> > q(qq);
    for (auto & x : q) {
      cin >> x.first >> x.second;
      x.first--;
      x.second--;
    }
    vector<vector<array<int, 2> > > sw(qq);
    vector<node> nd(n);
    LCA lca(v, nd);
    for (int m = 0; m < 32 / B; m++) {
      long long MSK = ((1LL << B) - 1) << (m * B);
      for (int i = 0; i < n; i++) {
        nd[i] = node(((1LL * a[i]) & MSK) >> (m * B));
        lca.jump[0][i].second = nd[i];
      }
      lca.a = nd;
      lca.update_jump();
      for (int j = 0; j < qq; j++) {
        auto ret = lca.query(q[j].first, q[j].second);
        vector<array<int, 2> > v;
        int cnt = 0;
        for (int i = 0; i < B; i++) {
          if (ret.a[i] != 1e9) {
            sw[j].push_back({ret.a[i], 1});
            sw[j].push_back({ret.a[B + i] + 1, -1});
          }
        }
      }
    }
    for (int i = 0; i < qq; i++) {
      sort(sw[i].begin(), sw[i].end());
      int cur = 0;
      int cnt = sw[i].size() / 2;
      int maxi = sw[i].size() / 2;
      for (int j = 0; j < sw[i].size(); j++) {
        cur += sw[i][j][1];
        maxi = max(maxi, cnt + cur);
      }
      cout << maxi << " \n"[i == qq - 1];
    }
  }

  // IF STUCK:
    // DIV CONQUER?
    // CONSIDER SMALL CASES
    // INDUCTION
  return 0;
}