# HackerEarth Dexters Random Generator problem solution

In this HackerEarth Dexter's Random Generator problem solution Dexter has recently constructed a random generator. This generator works on a tree of N nodes. The information about the tree has to be fed into the generator in order for it to start working.

Each node, u of the tree has a value A[u] associated with it. The generator works as follows:

It takes as input two integers, u and v. It then outputs two integers X and Y. X can be either A[u] or A[v], with equal probability. Now, the generator selects a node i randomly and with equal probability from the path u - v (including u and v) in the tree and outputs the value of Y as A[i].

Let the above process be denoted by: Process(u,v), which takes input a pair of integers and outputs a pair of integers (X, Y).

Now, Hannah has been invited to test the random generator constructed by Dexter. Hannah has Q questions. Each question is as follows:

Hannah selects two nodes u and v of the tree. She wants to know the maximum value of Query(u,v).

## HackerEarth Dexter's Random Generator problem solution.

`#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 100;const int LIM = 31;const int LOGN = 20;vector <int> g[N];int a[N];int trie[N * LIM] , to[N * LIM], ptr;int root[N];int insert(int num, int lev, int root) {  int newRoot = ++ptr;  int cur = newRoot;  for(int i = LIM-1 ; i >= 0 ; i --) {    int bit = (num >> i) & 1;    to[cur][bit^1] = to[root][bit^1];    to[cur][bit] = ++ptr;    root = to[root][bit];    cur = to[cur][bit];    trie[cur] = lev;  }  return newRoot;}int query(int num, int lev, int root) {  int cur = root;  int ret = 0;  for(int i = LIM-1 ; i >= 0 ; i --) {    int bit = (num >> i) & 1;    if(to[cur][bit ^ 1] && trie[to[cur][bit^1]] >= lev) {      ret = ret * 2 + 1;      cur = to[cur][bit ^ 1];    }    else {      ret = ret * 2;      cur = to[cur][bit];    }  }  return ret;}int level[N] , P[LOGN][N];void dfs(int u , int p){  P[u] = p;  for(int i = 1 ; i < LOGN ; i ++)    P[i][u] = P[i-1][P[i-1][u]];  root[u] = insert(a[u], level[u], root[p]);  for(int i = 0 ; i < g[u].size();i++)    if(g[u][i] != p){      level[g[u][i]] = level[u] + 1;      dfs(g[u][i] , u);    }}inline int LCA(int x , int y){  if(level[x] < level[y])swap(x , y);  int lg = 1; for(;(1<<lg) <= level[x] ; lg ++);lg--;  for(int i = lg ; i >= 0 ; i--)    if(level[x] - (1<<i) >= level[y])      x = P[i][x];  if(x == y)return x;  for(int i = lg ; i >= 0 ; i--)    if(P[i][x] != -1 && P[i][x] != P[i][y]){      x = P[i][x];      y = P[i][y];    }  return P[x];}int main() {  ptr = 1;  int n,m; cin >> n >> m;  for(int i = 1; i <= n; i ++) cin >> a[i];  for(int i = 1; i < n; i ++) {    int u,v; cin >> u >> v;    g[u].push_back(v);    g[v].push_back(u);  }  dfs(1,0);  while(m --) {    int u,v; cin >> u >> v;    int lca = LCA(u,v);    int lev = level[lca];     int ans = query(a[u], lev, root[u]);    ans = max(ans, query(a[u], lev, root[v]));    ans = max(ans, query(a[v], lev, root[u]));    ans = max(ans, query(a[v], lev, root[v]));    cout << ans << endl;  }  return 0;}`